問題文

この問題はリアクティブ形式の（ジャッジ側のプログラムと対話的に実行する必要がある）問題です。

最初に $3$ 個の正整数 $N, B, Q$ が与えられます。

長さ $N$ の正整数列 $a$ と $N$ 以下の正整数 $i$ に対し、$a_i$ で $a$ の $i$ 個目の成分を表します。（$a = (a_1, a_2, \ldots, a_N)$）

$N$ 以下の正整数 $i$ に対し、以下を満たす $N$ 以下の正整数 $j$ 全体の集合を $S_i$ と置きます。

• ある非負整数 $d$ が存在して、$i$ は $2^{-d} j$ を超えない最大の整数 $\lfloor 2^{-d} j \rfloor$ である。

大雑把に言うと、$S_i$ は二進法で書き表した時に $i$ を先頭に含む $N$ 以下の正整数全体の集合です。

二進法大好きbotは二進法が大好きなbotです。

あなたと二進法大好きbotは長さ $N$ の非負整数列 $A$ を共有しており、最初は $A$ が以下を満たしています。

• $N$ 以下の任意の正整数 $i$ に対し、$A_i = i$ である。

以下の一連のやり取り（以下、クエリと呼ぶ）を $Q$ 回行うことで $A$ を更新します。

1. まず二進法大好きbotが $N$ 以下の正整数 $i$ と非負整数 $d$ を選んであなたに教える。
2. 続いて $S_i$ の各要素 $j$ に対し、$A$ の $j$ 個目の成分を $A_j^d + 1$ で置き換えることで $A$ を更新する。
3. 更新後の $A$ に対し、$S_i$ の各要素 $j$ をわたる $A_j$ の総和 $\sum_{j \in S_i} A_j$ を $B$ で割った余りをあなたが答える。（以下この値を、このクエリに対する回答と呼ぶ）

クエリは厳密に順番を守って処理する必要があります。特に、$i, d$ が選ばれるのはそれ以前のクエリに対する回答をあなたが答え終えた後です。

入出力

最初に $N, B, Q$ が標準入力から半角空白区切りで $1$ 行目に与えられます。

$N$ $B$ $Q$

その後で $Q$ 回のクエリを処理してください。クエリは標準入出力を用いて以下の形式で行います：

1. まず二進法大好きbotが選んだ $i, d$ が半角空白区切りで $1$ 行で与えられます。ただし $i, d$ が与えられるのはそれ以前のクエリに対する回答を出力し終えている時に限られます。

$i$ $d$

2. 次にクエリに対する回答を $1$ 行で出力してください。

($\sum_{j \in S_i} A_j$ を$B$ で割った余り)

最後に改行してください。

制約

入力は以下の制約を満たします：

• $N$ は $1 \leq N \leq 1.5 \times 10^6$ を満たす整数である。
• $B$ は $1 \leq B \leq 10^2$ を満たす整数である。
• $Q$ は $1 \leq Q \leq 1.5 \times 10^3$ を満たす整数である。
• 各クエリにおいて二進法大好きbotが選ぶ $i, d$ は以下を満たす。
• $i$ は $1 \leq i \leq N$ を満たす整数である。
• $d$ は $0 \leq d \leq 10^{18}$ を満たす整数である。

注意

リアクティブ形式の問題に慣れてない方は、リアクティブ形式の問題についてのまとめも参考にしてください。

この問題において、以下の指示に従っていない提出のジャッジ結果は保証しません：

• 出力は指定された形式に厳格に従ってください。例えば余計な空白を入れたりしないでください。
• 出力を行うたびに末尾に改行を入れて標準出力をflushしてください。
• 全ての回答を出力し終えた後はプログラムをすぐに終了させてください。

サンプル

3 4 5
2 1
3 1
1 2
2 2
3 3

3
0
1
1
2