填充三角形

题目描述

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

给定序列 $P = ((a_1, c_1), (a_2, c_2), ..., (a_M, c_M))$，它是序列 $A = (A_1, A_2, ..., A_N)$ 的游程压缩结果，其中 $A$ 由不超过 $6$ 的非负整数组成。

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

你将在每个方块上写一个数，使得满足以下条件，其中 $B_{i,j}$ 表示从上数第 $i$ 列、从左数第 $j$ 个方块上写的数：

对于所有满足 $1 \le i \le N$ 的整数 $i$，有 $B_{N,i} = A_{i}$。

对于所有满足 $1 \le j \le i \le N-1$ 的整数对 $(i, j)$，有 $B_{i,j} = (B_{i+1,j} + B_{i+1,j+1}) \bmod 7$。

枚举从上数第 $K$ 列的方块上写的数。

什么是游程压缩？

游程压缩是将给定序列 $A$ 转换为整数对序列的转换，按以下步骤进行。

在相邻两个元素不同的位置将 $A$ 切开。

对于切出的每个子序列 $B$，用“$B$ 由哪个数组成”和“$B$ 的长度”组成的整数对替换 $B$。

在保持顺序的情况下，构造替换后的整数对组成的序列。

输入格式

输入按以下格式从标准输入给出：

N M K
a_1 c_1
a_2 c_2
⋮
a_M c_M

输出格式

按以下格式打印答案。保证在本问题的约束下答案唯一。

B_{K,1} B_{K,2} … 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

数据范围

• $1 \le N \le 10^9$
• $1 \le M \le \min(N, 200)$
• $1 \le K \le \min(N, 5 \times 10^5)$
• $0 \le a_i \le 6$
• $1 \le c_i \le N$
• $\sum_{i=1}^M c_i = N$
• 输入中的所有值均为整数。