该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

希望你在[广告位招租]中，找到答案。

题目描述

谷米莱莉娅的朋友小衣最近在深入学习计算机体系结构，迷上了CPU。她花了一个学期深入研究了[广告位招租]的[广告位招租]架构，然后决定开始自己造CPU。她的CPU是一个非常精致而简约的结构，也就是说它是一个有$n$个结点的链，按顺序将结点编号为$1,2,\dots,n$。CPU的结点类型有两种，第一种叫读取结点，第二种叫写入结点。顾名思义，读取结点可以读取寄存器的数据，写入结点可以将数据写入寄存器。

为了进行庞大的数据交互，小衣一共使用了32个寄存器来交互数据，编号为$0,1,2,\dots,31$。同时她准备了$m$条指令用来测试她的CPU。她需要将这$m$条指令按顺序塞入她的CPU。

为了体现她造的CPU的优雅，小衣设计的指令集非常特殊。每一个指令只有一个内容$x$，表示这个指令需要使用第$x$个寄存器。每一个指令将从CPU的开头，也就是第$1$个结点开始，一路运行到第$n$个结点。由于小衣的CPU精通量子力学，对于任意一条到达第$i$个结点的指令，它会花$1$个单位时间准备，然后在这个单位时间的末尾从第$i$个结点自动跳到第$i+1$个结点。当离开结点的瞬间，数据就会被读取或写入。同理，将这个指令放到第一个结点不需要花费时间，指令从第$n$个结点离开需要花费$1$个单位时间。经过读取结点，CPU就会读取该寄存器的数据，而经过写入结点就会写入数据（至于写入数据从哪来的，小衣表示她的CPU会自动处理，不需要担心这些）。

小衣很快实现了一个优秀的流水线CPU，也就是说，她可以每隔一秒就塞入一个指令，让这些指令在CPU上同时跑。

然后小衣就遇到了data hazard^[1]。具体来说，假如第$i$和第$j$条（$i<j$）指令需要用到同一个寄存器，而且这个寄存器的值在执行第$i$条指令后被写入了，那么对于CPU上的任何一个结点，它所需求（当然，无论是读取还是写入都算）的寄存器的值在执行第$j$条指令的时候应该是被写入后的值。这在单循环的CPU里自然没有问题，但在流水线的CPU中，就有可能出现在第$i$个指令对寄存器的写入还没发生之前，第$j$条指令就已经被塞入CPU的情况。这种时候，CPU的数据就会发生错乱，而这自然是追求优雅的小衣深恶痛绝的。因此，为了避免data hazard的产生，对于这样满足条件的$i,j$，小衣需要确保在第$i$条指令的写入完成后再塞入第$j$条指令。

同时，小衣还不满足于静态的CPU，因为她认为一成不变也是不优雅的。她还打算进行$q$次修改。每一次修改会将某个结点的类型改变。现在小衣想知道，每一次修改后，她跑完所有测试指令需要花费的最短时间是多少。

输入格式

输入第一行包含三个整数$n,m,q$。

接下来一行包含$n$个整数，每个整数表示对应的结点是读取结点还是写入结点，分别用0和1表示。

接下来一行包含$m$个整数，每个整数表示对应的指令使用的寄存器。

接下来$q$行，每行包含两个整数$opt,id$。若第一个整数是$0$，表示将某个结点修改成读取结点；若第一个整数是$1$，表示将某个结点修改成写入结点；$id$表示修改结点的编号。

输出格式

输出包含$q+1$行，每行仅包含一个整数，分别表示初始状态和每一次修改后需要花费的最短时间。

样例

3 3 3
0 1 0
0 1 0
0 2
1 2
1 3

5
5
5
6

10 14 9
1 0 0 0 1 1 1 0 1 0
7 6 2 1 5 7 5 6 1 6 7 3 7 1
0 2
1 9
0 9
0 4
1 7
1 8
1 8
0 8
1 6

44
44
44
38
38
38
41
41
38
38

对于第一个样例，初始状态下，直接每一秒放一个就能满足限制；第一次修改与第二次修改后，与初始状态的策略一致；第三次修改后，第三条指令需要等第一条指令离开CPU才能放入。

数据范围

对于$100\%$的数据，$1\le n\le10^5,1\le m\le 10^5,0\le q\le 10^5$。

本题的每个测试点均为7分。