D - 暴露 Editorial /

Time Limit: 4 sec / Memory Limit: 256 MB

問題文

1 から N までの番号が付けられた N 人の生徒からなるある学園で期末試験が行われた。試験は 100 点満点で、どの生徒も非負の整数の得点を獲得した。

この学園ではどの生徒も自分の得点と全受験者の合計点を通知されるが、それ以外の情報は通知されない。

しかしながらどの生徒も他の生徒の得点が気になる。そのため生徒は他の生徒から得点を聞き出し、それらの値を基に他の生徒の得点を予想することにしている。

学園の教師であり、生徒が他の生徒の得点をどれくらい正確に把握しているのかが気になったあなたは、生徒の行動によってどのくらい得点が特定できているのかを調査することにした。

具体的には、以下に示す M 個の情報クエリあるいは質問クエリを番号の昇順に処理した際の質問クエリの答えを計算することにした。

  • クエリには 1 から M までの番号が付けられている。どのクエリも 3 つの整数 a_i (0 ≦ a_i ≦ 1), b_i (1 ≦ b_i ≦ N), c_i (1 ≦ c_i ≦ N, b_i≠c_i) によって定められる。
  • a_i = 0 のとき、クエリ i は情報クエリである。これは、生徒 b_i が生徒 c_i の得点を知ったことを表す。
  • a_i = 1 のとき、クエリ i は質問クエリである。これは、生徒 b_i がクエリ i までの情報クエリと元々知っている情報のみで、生徒 c_i の得点が何点以上何点以下であると判定できるのかを答えなければならないことを表す。

入力

入力は以下の形式で標準入力から与えられる。

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
  • 1 行目には、学園の生徒数 N (2 ≦ N ≦ 50) が与えられる。
  • 2 行目から N 行には、生徒の得点が与えられる。N 行のうち i (1 ≦ i ≦ N) 行目には、生徒 i が獲得した得点 s_i (0 ≦ s_i ≦ 100) が与えられる。
  • N+2 行目には、クエリ数 M (1 ≦ M ≦ 5,000) が与えられる。
  • N+3 行目から M 行には、クエリの情報が与えられる。M 行のうち i (1 ≦ i ≦ M) 行目には、クエリ i を定める 3 つの整数 a_i (0 ≦ a_i ≦ 1), b_i (1 ≦ b_i ≦ N), c_i (1 ≦ c_i ≦ N, b_i≠c_i) が空白区切りで与えられる。
  • 1 ≦ i ＜ j ≦ M となる整数 i, j に対して、a_i = a_j = 0 ならば、b_i ≠ b_j または c_i ≠ c_j が成り立ちます。
  • 入力では 1 ≦ i ≦ M を満たすある整数 i において a_i = 1 であること (すなわち少なくとも 1 つは質問クエリがあること) が保証されています。

出力

M 個のクエリ中の質問クエリ数を Q 個としたとき、出力は Q 行からなる。Q 行のうち i (1 ≦ i ≦ Q) 行目には、i 番目の質問クエリに対する答えを出力せよ。i 番目の質問クエリに対する答えが、x 点以上 y 点以下であるという答えならば、x と y をこの順に空白区切りで出力せよ。出力の末尾にも改行を入れること。

入力例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

出力例1

80 100
80 80
50 100

生徒は 4 人であり、クエリは 6 個ある。

  • クエリ 1 は情報クエリである。生徒 2 は生徒 3 の得点が 70 点であることを知る。
  • クエリ 2 は情報クエリである。生徒 4 は生徒 2 の得点が 90 点であることを知る。
  • クエリ 3 は質問クエリである。この時点で生徒 2 は合計点が 80+90+70+100=340 点であること、生徒 2 の得点が 90 点であること、生徒 3 の得点が 70 点であることを知っているので、生徒 4 の得点は 80 点以上 100 点以下であることがわかる。よって出力の 1 行目は 80 100 となる。
  • クエリ 4 は情報クエリである。生徒 2 は生徒 4 の得点が 100 点であることを知る。
  • クエリ 5 は質問クエリである。この時点で生徒 2 は合計点および生徒 1 以外すべての生徒の得点を知っているので、生徒 1 の得点はちょうど 80 点であることがわかる。よって出力の 2 行目は 80 80 となる。
  • クエリ 6 は質問クエリである。この時点で生徒 4 は合計点が 340 点であること、生徒 2 の得点が 90 点であること、生徒 4 の得点が 100 点であることを知っているので、生徒 1 の得点は 50 点以上 100 点以下であることがわかる。よって出力の 3 行目は 50 100 となる。

入力例2

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

出力例2

0 43
12 12

既に得点を知っている相手に対して質問クエリが飛んで来る場合もあります。

入力例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

出力例3

0 80
18 18
0 97
0 86
0 100