#P18073. Tetris

Tetris

Tetris

题目描述

有 nn 种方块,编号为 11 到 nn。无限方块序列按袋生成:每袋恰好包含每种方块一次,袋内顺序任意,不同袋相互独立。把这些排列依次连接,得到整个序列。

小 C 已经取走了 xx 个方块,接下来连续 mm 个方块的记录为 f1,…,fmf_1,\ldots,f_m,对应整个序列的第 x+1x+1 到第 x+mx+m 项。其中 fi=0f_i=0 表示该位置的种类未知,其余值表示已知种类。

求所有可能的 x mod nx\bmod n 的数量,以及这些余数的按位异或和。可能不存在任何符合记录的序列,此时输出 0 0。

还会有 qq 次修改,每次将一个记录位置 faf_a 改为 bb,其中 b=0b=0 仍表示未知。修改依次累积生效。你需要在初始时刻以及每次修改后回答。

输入格式

第一行三个整数 n,m,qn,m,q。第二行 mm 个整数 f1,…,fmf_1,\ldots,f_m。接下来 qq 行,每行两个整数 a,ba,b。

1≤n≤10181\le n\le10^{18},1≤m≤5×1051\le m\le5\times10^5,0≤q≤5×1050\le q\le5\times10^5,0≤fi,b≤n0\le f_i,b\le n,1≤a≤m1\le a\le m。

输出格式

输出 q+1q+1 行,每行两个整数。第 ii 行表示前 i−1i-1 次修改后的合法余数数量和异或和。每个合法余数只计一次。

样例 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