고속도로

어떤 나라에는 $n$개의 도(道)에 걸쳐 도시들을 잇는 일방통행 고속도로 망이 있습니다. 도는 $1$번부터 $n$번까지 번호가 매겨져 있습니다. 한 도시에서 나가는 직행 고속도로는 오직 바로 다음 번호의 도에 있는 도시로만 이어질 수 있습니다. 고속도로마다 차선 수가 다릅니다. 운전자는 어떤 도시에 도착하면 반드시 타고 온 고속도로에서 빠져나오며, 여행을 계속하려면 새 고속도로에 올라타야 합니다. 두 도시 사이를 달리는 동안에는 직전 도시에서 올라탄 차선 하나를 계속 유지해야 합니다.

운전자들은 정해진 두 도시 사이를 잇는 서로 다른 경로의 수에 관심이 있습니다. 두 경로는 지나는 도시가 정확히 같고, 도시 사이를 잇는 차선까지 모두 같을 때에만 동일한 경로로 봅니다. 도로망은 끊임없이 개보수·확장되므로 연결 정보를 자주 갱신해야 합니다.

중간에 들어오는 갱신을 반영하면서 운전자들의 질의에 차례로 답하세요. 각 경로 수는 고정된 정수 $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$번째 줄은 그 도의 $i$번 도시에서 나가는 고속도로들을 설명하며, $m_{k+1}$개의 정수 $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$번 도시와 $k+1$번 도의 $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 줄로 끝납니다. e 0 0 0 0 줄을 제외하면 질의와 갱신은 모두 합쳐 최대 $5000$개입니다.

질의마다 한 줄씩, 입력에 나온 순서대로 정수 하나를 출력합니다. 각 줄에는 질의한 두 도시 사이의 경로 수를 $d$로 나눈 나머지 하나가 들어갑니다. 출력하는 줄 수는 질의 수와 같아야 합니다.