In Byteotia, there is a network of one-way highways connecting cities in $n$ provinces. The provinces are numbered from 1 to $n$. From a given city, a direct highway can only lead to a city located in the next province (according to the numbering). Highways differ in the number of lanes. After arriving at a city, a driver always leaves the highway and must enter a new one if they wish to continue their journey. Between cities, a driver must stay in the same lane they entered in the last city.

Byteotian drivers are interested in the number of different routes leading between selected pairs of cities. Two routes are considered identical only if they pass through exactly the same cities and use the same lanes between cities. Due to constant repairs and network expansion, information about connections needs to be updated frequently.

Help answer a series of drivers' questions, taking into account updates to highway information received in the meantime. It is sufficient to provide the remainder of the division of the obtained number by a given integer $d$.

Task

Write a program that: reads the divisor $d$, the number of provinces, the number of cities in each province, the description of the initial highway network, and a series of questions and updates, for each question, calculates the number of routes mentioned in the question, taking into account previous updates, * outputs the remainders of the division of the obtained numbers by $d$.

Input

The first line contains two integers $d, n$ ($2 \le d \le 40000$, $2 \le n \le 30000$). The second line contains the sequence $m_1, m_2, \dots, m_n$, where $m_k$ is the number of cities in the $k$-th province ($1 \le m_k \le 10$). Next, sections corresponding to provinces numbered $1, 2, \dots, n-1$ appear in order. The province numbered $k$ is described in the next $m_k$ lines. The line numbered $i$ in a given section describes the highways leaving the $i$-th city in province $k$ and contains the numbers $p_k(i, 1), p_k(i, 2), \dots, p_k(i, m_{k+1})$ ($0 \le p_k(i, j) \le 10^9$), where $p_k(i, j)$ denotes the number of lanes on the highway leading from the $i$-th city in the $k$-th province to the $j$-th city in the next province (numbered $k+1$).

Subsequent lines of the input contain a certain number of questions and updates. A line starting with the character q, followed by four integers $k, i, l, j$, denotes a question about the number of routes leading from the $i$-th city in the $k$-th province to the $j$-th city in the $l$-th province ($1 \le k < l \le n$, $1 \le i \le m_k$, $1 \le j \le m_l$). A line starting with the character u, followed by four integers $k, i, j, r$, denotes a change to $r$ in the number of available lanes between the $i$-th city of the $k$-th province and the $j$-th city of the next province ($1 \le k < n$, $1 \le i \le m_k$, $1 \le j \le m_{k+1}$, $0 \le r \le 10^9$). The input is terminated by a line of the form e 0 0 0 0.

In total, there are no more than 5000 questions and updates, not counting the e 0 0 0 0 line.

Output

Your program should output a series of lines, each containing one integer, representing the answers to consecutive questions. The number of lines in the output should be equal to the number of questions. Each line must contain one integer, equal to the remainder of the division by $d$ of the number of routes between the considered pair of cities.

Examples

Input 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

Output 1

2
1
2
0
2
4