当前没有测试数据。

填充三角形

得分：600分

问题描述

一堆方块堆叠成了一个三角形。从顶部开始的第i列有i个方块。

给定一个序列 $P = ((a_1, c_1), (a_2, c_2), ..., (a_M, c_M))$，它是一个由非负整数构成的序列$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$ 的所有整数，有 $B_{N,i} = A_{i}$。
• 对于所有整数对 $(i, j)$，满足 $1 \leq j \leq i \leq N-1$，有 $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}$ ```

---

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