配点 : $600$ 点

問題文

ブロックが三角形状に $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$ 段目のブロックに書かれた数を列挙してください。

制約

• $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}$

6 3 4
2 3
5 2
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

1 1 1
6 1

6

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

1 0 4 2 5 5 5 6 3