Tajaはよくおもちゃ屋のそばを通り、店の窓際に置かれた電子掲示板に表示されている2つの整数を眺めていた。店の窓には数種類のおもちゃが並んでいるが、掲示板の数字は実際の在庫状況と一致していないことがある。これは、購入されたおもちゃがすぐに窓から取り除かれるわけではなく、購入から一定時間が経過した後に取り除かれるためである。この時間は、おもちゃの種類によって異なる。

おもちゃは $n$ 種類ある。各種類について、初期の在庫数 $c_i$ と、購入されてから窓から取り除かれるまでの時間 $t_i$ 分がわかっている。毎分、以下のことが順番に起こる。

• 購入から指定された時間が経過したおもちゃが、店の窓から取り除かれる。
• 電子掲示板が更新される。
• 新しい客が来店し、在庫のあるおもちゃを必ず1つ購入する。

Tajaは掲示板の数字の意味に興味を持ち、最近それを突き止めた。両方の数字とも、店で購入可能なおもちゃの種類数を表しているが、1つ目の数字は「現時点まで在庫がある可能性がある種類数」であり、2つ目の数字は「現時点まで確実に在庫がある種類数」である。Tajaは、この掲示板が客にとってどれほど有益かにも興味がある。そのため、客の行動をモデル化し、掲示板を更新するプログラムが必要となった。

あなたのタスクは、毎分ごとの電子掲示板の数字を計算することである。

入力

入力の最初の行には、おもちゃの種類数を表す整数 $n$ ($1 \le n \le 10^5$) が与えられる。

続く $n$ 行には、各 $i$ 番目のおもちゃの種類について、初期在庫数 $c_i$ と購入後に窓から取り除かれるまでの時間 $t_i$ ($1 \le c_i \le 10^5, 1 \le t_i \le 100$) が与えられる。

次の行には、客の数を表す整数 $k$ ($1 \le k \le 10^5$) が与えられる。

続く $k$ 行には、各 $i$ 分目に窓から取り除かれたおもちゃの数 $q_i$ と、それらのおもちゃの番号 $p_1, p_2, \dots, p_{q_i}$ が与えられる。

出力

$k$ 行を出力せよ。各行には、その $i$ 分目の開始時点における電子掲示板の数字 $a_i$ と $b_i$ を出力すること。

入出力例

入出力例 1

3
1 2
2 1
3 3
6
0
0
0
3 1 2 3
0
1 2

3 3
3 2
3 2
2 2
2 2
1 1

注記

上記の例では、店の窓には1種類目のおもちゃが1個、2種類目が2個、3種類目が3個あり、購入からそれぞれ2分、1分、3分後に取り除かれる。掲示板の数字は以下の順序で変化する。

• 3/3: 最初の客が来る前は客がいなかったため、どの種類のおもちゃも購入可能である。
• 3/2: 最初の客が1種類目のおもちゃを購入した可能性があるため、2番目の客がそれを購入できるという確信は持てない。
• 3/2: 1種類目も2種類目も窓から取り除かれていないため、最初の客は3種類目のおもちゃを購入したことになる。2番目の客が何を購入したかはまだ判断できない。
• 2/2: 1種類目のおもちゃはもう残っていない。
• 2/2: 窓から取り除かれたおもちゃはないため、前の客は3種類目のおもちゃを購入したことになる。
• 1/1: 3種類目のおもちゃが1個だけ残っている。