Problem Description

A certain school with $ N $ students numbered from $ 1 $ to $ N $ has conducted a final exam. The exam is scored out of $ 100 $ points, and each student has received a non-negative integer score.

In this school, each student is informed of their own score and the total score of all test-takers, but no other information is provided.

However, students are curious about each other's scores. Therefore, they decide to ask other students for their scores and use these values to guess other students' scores.

As a teacher in this school, you are curious about how accurately students can determine each other's scores based on their actions. Specifically, you decide to investigate how well scores can be pinpointed by processing the following $ M $ information queries or question queries in ascending order of their numbers.

• Each query is numbered from $ 1 $ to $ M $ and is defined by three integers $a_i\ (0\ ≦\ a_i\ ≦\ 1)$, $b_i\ (1\ ≦\ b_i\ ≦\ N)$, $c_i\ (1\ ≦\ c_i\ ≦\ N,\ b_i≠c_i)$.
• When $ a_i $ = $ 0 $, query $ i $ is an information query, indicating that student $ b_i $ has learned student $ c_i $'s score.
• When $ a_i $ = $ 1 $, query $ i $ is a question query, indicating that student $ b_i $ must answer what range of scores student $ c_i $ can have based only on the information queries processed so far and the information they already know.

Input Format

The input is given from the standard input in the following format:

$ N $ $ s_1 $ $ s_2 $ : $ s_N $ $ M $ $ a_1 $ $ b_1 $ $ c_1 $ $ a_2 $ $ b_2 $ $ c_2 $ : $ a_M $ $ b_M $ $ c_M $

• The first line contains the number of students $N\ (2\ ≦\ N\ ≦\ 50)$.
• The next $ N $ lines contain the scores of the students. The $i\ (1\ ≦\ i\ ≦\ N)$th line contains the score $s_i\ (0\ ≦\ s_i\ ≦\ 100)$ of student $ i $.
• The $ N+2 $th line contains the number of queries $M\ (1\ ≦\ M\ ≦\ 5,000)$.
• The next $ M $ lines contain the query information. The $i\ (1\ ≦\ i\ ≦\ M)$th line contains three integers $a_i\ (0\ ≦\ a_i\ ≦\ 1)$, $b_i\ (1\ ≦\ b_i\ ≦\ N)$, $c_i\ (1\ ≦\ c_i\ ≦\ N,\ b_i≠c_i)$ separated by spaces.
• For integers $ i $, $ j $ such that $1\ ≦\ i\ ＜\ j\ ≦\ M$, if $ a_i $ = $ a_j $ = $ 0 $, then $ b_i $ ≠ $ b_j $ or $ c_i $ ≠ $ c_j $.
• The input guarantees that there is at least one question query, i.e., $ a_i $ = $ 1 $ for some integer $ i $ satisfying $1\ ≦\ i\ ≦\ M$.

Output Format

If there are $ Q $ question queries among the $ M $ queries, the output consists of $ Q $ lines. The $i\ (1\ ≦\ i\ ≦\ Q)$th line should contain the answer to the $ i $th question query. If the answer to the $ i $th question query is that student $ c_i $'s score is between $ x $ and $ y $ points, output $ x $ and $ y $ in this order separated by a space. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

4
80
90
70
100
6
0 2 3
0 4 2
1 2 4
0 2 4
1 2 1
1 4 1

Sample Output #1

80 100
80 80
50 100

Sample Input #2

3
25
12
31
3
1 1 2
0 1 2
1 1 2

Sample Output #2

0 43
12 12

Sample Input #3

7
32
19
22
25
23
17
18
11
0 1 2
0 4 5
0 1 4
0 2 3
0 2 7
1 1 5
1 2 7
1 2 1
0 4 3
1 4 2
1 6 7

Sample Output #3

0 80
18 18
0 97
0 86
0 100

Notes/Hints

Sample Explanation 1

There are $ 4 $ students and $ 6 $ queries.
- Query $ 1 $ is an information query. Student $ 2 $ learns that student $ 3 $'s score is $ 70 $ points.
- Query $ 2 $ is an information query. Student $ 4 $ learns that student $ 2 $'s score is $ 90 $ points.
- Query $ 3 $ is a question query. At this point, student $ 2 $ knows the total score is $ 80+90+70+100=340 $ points, their own score is $ 90 $ points, and student $ 3 $'s score is $ 70 $ points. Therefore, student $ 2 $ can determine that student $ 4 $'s score is between $ 80 $ and $ 100 $ points. Thus, the first line of output is 80 100.
- Query $ 4 $ is an information query. Student $ 2 $ learns that student $ 4 $'s score is $ 100 $ points.
- Query $ 5 $ is a question query. At this point, student $ 2 $ knows the scores of all students except student $ 1 $, so they can determine that student $ 1 $'s score is exactly $ 80 $ points. Thus, the second line of output is 80 80.
- Query $ 6 $ is a question query. At this point, student $ 4 $ knows the total score is $ 340 $ points, student $ 2 $'s score is $ 90 $ points, and their own score is $ 100 $ points. Therefore, student $ 4 $ can determine that student $ 1 $'s score is between $ 50 $ and $ 100 $ points. Thus, the third line of output is 50 100.

Sample Explanation 2

Question queries may be directed to students whose scores are already known.

见题面 Input 部分

见题面 Output 部分