问题描述

方块被堆叠成一个三角形。从上往下数，第 $i$ 列有 $i$ 个方块。

给定一个序列 $P = ((a_1, c_1), (a_2, c_2), ..., (a_M, c_M))$，它是一个由非负整数组成且小于等于 $6$ 的序列 $A = (A_1, A_2, ..., A_N)$ 的运行长度压缩结果。

• 例如，当 $A = (2, 2, 2, 5, 5, 1)$ 时，给定 $P = ((2, 3), (5, 2), (1, 1))$。

你需要在每个方块上写一个数字，使得满足以下条件，其中 $B_{i,j}$ 表示从上往下数第 $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