$T$ 個のテストケースについて、以下の問題を解いてください。

$M$ 行 $M$ 列のグリッドがあり、上から $i+1$ 行目、左から $j+1$ 行目のマスを $(i, j)$ と表します。
高橋くんは次のようなゲームをプレイしています。

• まずシード値 $s (0 \leq s < M)$ を決める。$(\mathrm{RNG}_s(N), \mathrm{RNG}_s(N+1))$ を高橋くんの最初の座標としてゲームを開始する。
• その後、ゲームをクリアするまで好きなだけ次の行動ができる。
  • 高橋くんのいる座標が $(X, Y)$ のとき、ゲームをクリアする。
  • 隣接するマスに単位時間かけて移動する。ただし、グリッドの外には移動できない。
    • マス $(i, j)$ は次の $8$ つのマスに（存在する場合）隣接する。
      • $(i-1, j-1)$
      • $(i-1, j)$
      • $(i-1, j+1)$
      • $(i, j-1)$
      • $(i, j+1)$
      • $(i+1, j-1)$
      • $(i+1, j)$
      • $(i+1, j+1)$

ここで、シード値が $s$ である線形合同法の $n$ 番目の出力を $\mathrm{RNG}_s(n)$ と表し、次によって定義します。

$\mathrm{RNG}_s(n) = \left\{
\begin{array}{ll}
s & (n = 1) \\
A \cdot \mathrm{RNG}_s(n-1) + B \pmod M & (n \geq 2)
\end{array}
\right.$

高橋くんはゲームが上手いので、最初に選んだシード値を $s$ として、ゲームを開始してからクリアするまでにかかる時間 $D_s$ を最小化するよう最適に行動します。
$s$ として考えられる値は $M$ 通りあります。$(D_s, s)$ を辞書順で昇順に並べたときの $K$ 番目の値の組を求めてください。

なお、$(a,b)$ が $(c,d)$ よりも辞書順で小さいとは、以下のいずれかが成り立つことをいいます。

• $a<c$
• $a=c$ かつ $b<d$

• $1 \leq T \leq 100$
• $1 \leq N \leq 10^{18}$
• $2 \leq M \leq 10^{9}$
• $0 \leq X,Y < M$
• $M$ は素数
• $1 \leq K \leq M$
• $1 \leq A < M$
• $0 \leq B < M$
• 入力はすべて整数である。

この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。

1. ($50$ 点)

• $2 \leq M \leq 10^{4}, 1 \leq N \leq 10^{4}$

2. ($100$ 点)

• $2 \leq M \leq 10^{4}$

3. ($350$ 点)

• $K = 1$

4. ($500$ 点)

• 追加の制約はない。

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

各テストケースは以下の形式で与えられる。

$T$ 行出力せよ。$i$ 行目には $i$ 番目のテストケースの答えとなる値の組を空白区切りで出力せよ。