题目描述

你生日时收到了一个由 M 个拼图片组成的拼图。每个拼图片上都写着一个编号——从 1 到 N 的某个整数（其中 N <= M）。允许存在多个拼图片具有相同的编号。

由于本题是“一维拼图”，拼图片的长度并不重要，真正重要的是：

• 它上面的编号；
• 左边的边类型；
• 右边的边类型。

拼图需要按照“一维”的方式排成一行，使得相邻拼图片的边能够“匹配”。

要求在拼图中恰好使用 N 个拼图片，并且在位置 K 上必须放置一个编号为 K 的拼图片。

拼图片左右边类型的编号如下：

• 类型 1：平滑边；

  

• 类型 2：上排比下排突出；

• 类型 3：下排比上排突出。

请编写程序 puzzle，完成以下两个任务：

1. 给定初始的所有拼图片，求满足条件的拼图摆放方案数，额外要求：

   • 编号为 1 的拼图片左边必须是平滑边（类型 1）；
   • 编号为 N 的拼图片右边必须是平滑边（类型 1）。

2. 在完成初始计算后，还会有若干次操作。每次操作为：

   • 添加一个新的拼图片，或
   • 删除一个已有的拼图片。

   每次操作后，都需要重新计算任务 1 的答案。

由于方案数可能很大，所有答案都对 1000000007 取模。

输入格式

第一行输入三个正整数 M, N, Q，分别表示：

• 当前给出的拼图片总数；
• 拼图中的最大编号（也就是最终拼图要使用的拼图片数量）；
• 操作次数。

接下来 M 行，每行输入三个正整数，表示一个拼图片：

• 上面的编号；
• 左边类型代码；
• 右边类型代码。

接下来 Q 行，每行表示一次操作，输入四个正整数：

• 第一个数表示操作类型：1 表示添加，2 表示删除；
• 第二个数表示拼图片上的编号；
• 第三个数表示左边类型代码；
• 第四个数表示右边类型代码。

保证对于删除操作，当前拼图片集合中一定存在一个参数完全相同的拼图片。
如果存在多个完全相同的拼图片，则删除任意一个即可。

输出格式

第一行输出初始状态下的答案，即任务 1 的方案数（对 1000000007 取模）。

接下来 Q 行，每行输出执行对应操作后的方案数（同样对 1000000007 取模）。

数据范围

• N <= M <= 100000
• 9 <= N <= 50000
• 1 <= Q <= 250000

样例

输入

8 3 5
1 1 1
1 1 2
1 2 1
2 1 2
2 3 3
2 1 3
3 2 1
3 3 2
1 3 3 1
2 3 2 1
1 2 3 2
1 2 3 2
1 3 2 1

输出

2
3
1
2
3
5

样例解释

初始时，拼图共有 2 种摆法，分别是：

• 选择输入中的第 1, 6, 7 个拼图片；
• 选择输入中的第 2, 5, 7 个拼图片。

第一次操作后，加入了一个编号为 3、左边类型为 3、右边类型为 1 的拼图片，于是新增了一种摆法，总方案数变为 3。

第二次操作后，删除了一个编号为 3、左边类型为 2、右边类型为 1 的拼图片，于是只剩下 1 种摆法。

之后又加入了两个参数完全相同的拼图片。需要注意的是：即便编号、左边类型、右边类型都相同，这两个拼图片依然被看作不同的拼图片，因此会产生不同的摆放方案。于是对应答案分别为 2 和 3。

最后一次操作再加入一个拼图片后，总方案数变为 5。