← 返回题目列表

AtCoder · abc251_h

Ex. 填充三角形

中文机器翻译题面 查看原题

分数: 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 为通过以下过程获得的整数对序列。
  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