分数: 600 点
问题陈述
块堆叠成三角形。 的 i从顶部开始的第列有 i 块。
给你一个序列 P = ((a_1, c_1), (a_2, c_2), ..., (a_M, c_M)) 这是序列的游程压缩的结果 A = (A_1, A_2, ..., A_N) 由小于或等于的非负整数组成 6.
- 例如,当 A = (2, 2, 2, 5, 5, 1),给你 P = ((2, 3), (5, 2), (1, 1)).
您将在每个块上写入一个数字,以满足以下条件,其中 B_{i,j} 表示要写在 j中从左边算起的第一个块 i从顶部开始的第列:
- 对于所有整数 i 这样 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 为通过以下过程获得的整数对序列。- 分裂 A 在两个不同元素彼此相邻的位置处关闭。
- 对于每个子序列 B 已被拆分,替换 B 与一个整数对“的数字 B 由“和”的长度组成 B".
- 构造一个由替换后的整数对组成的序列,而不改变顺序。
约束
- 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