#P18073. Tetris
Tetris
Tetris
题目描述
有 种方块,编号为 到 。无限方块序列按袋生成:每袋恰好包含每种方块一次,袋内顺序任意,不同袋相互独立。把这些排列依次连接,得到整个序列。
小 C 已经取走了 个方块,接下来连续 个方块的记录为 ,对应整个序列的第 到第 项。其中 表示该位置的种类未知,其余值表示已知种类。
求所有可能的 的数量,以及这些余数的按位异或和。可能不存在任何符合记录的序列,此时输出 0 0。
还会有 次修改,每次将一个记录位置 改为 ,其中 仍表示未知。修改依次累积生效。你需要在初始时刻以及每次修改后回答。
输入格式
第一行三个整数 。第二行 个整数 。接下来 行,每行两个整数 。
,,,,。
输出格式
输出 行,每行两个整数。第 行表示前 次修改后的合法余数数量和异或和。每个合法余数只计一次。
样例 1
输入
3 17 0
1 0 0 3 0 1 0 1 2 0 2 0 1 1 0 0 1
输出
1 2
样例 2
输入
4 10 4
0 4 0 0 1 0 0 3 1 0
5 0
5 3
10 4
9 3
输出
4 0
4 0
3 0
3 0
0 0
样例 3
输入
999999999999999999 10 10
0 0 0 0 314 15 0 0 9 0
1 0
9 287665588162745942
10 0
8 953846340212508779
10 275685051906270282
10 0
5 288735940850628909
9 14189307401575225
2 0
1 0
输出
999999999999999999 999999999999999999
999999999999999999 999999999999999999
999999999999999999 999999999999999999
999999999999999999 999999999999999999
999999999999999999 999999999999999999
999999999999999999 999999999999999999
999999999999999999 999999999999999999
999999999999999999 999999999999999999
999999999999999999 999999999999999999
999999999999999999 999999999999999999
999999999999999999 999999999999999999