题目描述

ブロックが三角形状に $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. 置き換えた整数の組を元の順番を保ったまま並べて列にする。

输入格式

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

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

题目大意

存在序列 $a_n$，将其压缩后给定。具体地，给定序列 $P$ 以如下形式：$((a_1, c_1), (a_2, c_2), \cdots, (a_m, c_m))$，表示序列 $a$ 中有 $c_1$ 个 $a_1$，$c_2$ 个 $a_2$，以此类推，且按序拼接。令序列 $a_n$ 为三角金字塔 $B$ 的第 $n$ 层，即 $B(n, i) = a_i$。特别地，该三角金字塔的递推式为 $ B(i, j) = (B(i + 1, j) + B(i + 1, j + 1)) \bmod{7} $。给定 $k$，求该三角金字塔第 $k$ 层的序列。

6 3 4
2 3
5 2
1 1

1 4 3 2

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

提示

制約

• $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$
• 入力される値はすべて整数

Sample Explanation 1

$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