問題文

ブロックが三角形状に $N$ 段並んでいます。上から $i$ 段目には $i$ 個のブロックが並んでいます。

$6$ 以下の非負整数からなる列 $A = (A_1, A_2, ..., A_N)$ を連長圧縮した列 $P = ((a_1, c_1), (a_2, c_2), ..., (a_M, c_M))$ が与えられます。

• 例えば $A = (2, 2, 2, 5, 5, 1)$ のとき $P = ((2, 3), (5, 2), (1, 1))$ になります。

上から $i$ 段目で左から $j$ 番目のブロックに書きこむ数を $B_{i,j}$ として、次の条件を満たすようにすべてのブロックに数を書きこみます。

• すべての $1 \\leq i \\leq N$ を満たす整数 $i$ について $B_{N,i} = A_{i}$
• すべての $1 \\leq j \\leq i \\leq N-1$ を満たす整数の組 $i,j$ について $B_{i,j}= (B_{i+1,j}+B_{i+1,j+1})\\bmod 7$

上から $K$ 段目のブロックに書かれた数を列挙してください。

連長圧縮とは？ 数列 $A$ を以下の手続きによって整数の組からなる列に変換することを連長圧縮と呼びます。

1. $A$ を異なる要素が隣り合っている部分で分割する。
2. 分割した各数列 $B$ に対して、$B$ を 「$B$ を構成する数」 と 「$B$ の長さ」 からなる整数の組に置き換える。
3. 置き換えた整数の組を元の順番を保ったまま並べて列にする。

制約

• $1 \\leq N \\leq 10^9$
• $1 \\leq M \\leq \\min(N, 200)$
• $1 \\leq K \\leq \\min(N,5 \\times 10^5)$
• $0 \\leq a_i \\leq 6$
• $1 \\leq c_i \\leq N$
• $\\sum_{i=1}^M c_i = N$
• 入力される値はすべて整数

入力

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

$N$ $M$ $K$ $a_1$ $c_1$ $a_2$ $c_2$ $\\vdots$ $a_M$ $c_M$

出力

答えを以下の形式で出力せよ。なお、制約下において答えは一意に定まることが保証される。

$B_{K,1}$ $B_{K,2}$ $\\dots$ $B_{K,K}$

入力例 1

6 3 4
2 3
5 2
1 1

出力例 1

1 4 3 2

$A = (2,2,2,5,5,1)$ です。また、ブロックに書かれる数は次のようになります。

     3
    5 5
   5 0 5
  1 4 3 2
 4 4 0 3 6
2 2 2 5 5 1

入力例 2

1 1 1
6 1

出力例 2

6

入力例 3

111111111 9 9
0 1
1 10
2 100
3 1000
4 10000
5 100000
6 1000000
0 10000000
1 100000000

出力例 3

1 0 4 2 5 5 5 6 3