在 Byteotia 存在一个由 $n$ 个省份的城市组成的单向高速公路网络。省份编号从 $1$ 到 $n$。从给定的城市出发，直达高速公路只能通往编号相邻的下一个省份的城市。高速公路的车道数量各不相同。司机在到达一个城市后，必须离开当前高速公路并驶入一条新的高速公路，如果他想继续旅程的话。在城市之间，司机必须始终保持在进入该城市时所选定的车道上。

Byteotia 的司机们对连接选定城市对之间的不同路径数量很感兴趣。只有当两条路径经过完全相同的城市序列，且在城市之间经过的车道也完全相同时，我们才认为这两条路径是相同的。由于不断的维修和网络扩建，有关连接的信息需要经常更新。

请帮助回答司机们的一系列询问，同时考虑在此期间收到的有关高速公路信息的更新。你只需要输出所得路径数量除以给定的整数 $d$ 后的余数。

题目描述

编写一个程序，完成以下任务： 读取除数 $d$、省份数量、每个省份的城市数量、高速公路网络的初始描述以及一系列询问和更新； 对于每个询问，计算询问中提到的路径数量，同时考虑之前的更新； * 输出所得路径数量除以 $d$ 的余数。

输入格式

第一行包含两个整数 $d, n$ ($2 \le d \le 40000, 2 \le n \le 30000$)。第二行包含序列 $m_1, m_2, \dots, m_n$，其中 $m_k$ 是第 $k$ 个省份的城市数量 ($1 \le m_k \le 10$)。接下来依次出现对应于编号为 $1, 2, \dots, n-1$ 的省份的段。第 $k$ 个省份由接下来的 $m_k$ 行描述。该段中的第 $i$ 行描述了从第 $k$ 个省份的第 $i$ 个城市出发的高速公路，包含数字 $p_k(i, 1), p_k(i, 2), \dots, p_k(i, m_{k+1})$ ($0 \le p_k(i, j) \le 10^9$)，其中 $p_k(i, j)$ 表示从第 $k$ 个省份的第 $i$ 个城市到下一个省份（编号为 $k+1$）的第 $j$ 个城市的高速公路车道数。

输入的后续行包含一定数量的询问和更新。以字符 q 开头的行，后跟四个整数 $k, i, l, j$，表示询问从第 $k$ 个省份的第 $i$ 个城市到第 $l$ 个省份的第 $j$ 个城市之间的路径数量 ($1 \le k < l \le n, 1 \le i \le m_k, 1 \le j \le m_l$)。以字符 u 开头的行，后跟四个整数 $k, i, j, r$，表示将第 $k$ 个省份的第 $i$ 个城市与下一个省份的第 $j$ 个城市之间的可用车道数更改为 $r$ ($1 \le k < n, 1 \le i \le m_k, 1 \le j \le m_{k+1}, 0 \le r \le 10^9$)。输入以 e 0 0 0 0 结尾。

询问和更新的总数不超过 $5000$（不计入 e 0 0 0 0 行）。

输出格式

你的程序应输出一系列行，每行包含一个整数，作为对后续询问的回答。输出的行数应等于询问的次数。每一行必须包含一个整数，等于路径数量除以 $d$ 的余数。

样例

输入 1

5 4
2 2 1 3
1 8
1 0
1
2
0 1 2
q 2 2 3 1
q 1 2 3 1
q 1 2 4 3
q 1 2 4 1
q 1 1 4 2
u 2 2 1 1
q 1 1 4 2
e 0 0 0 0

输出 1

2
1
2
0
2
4