At P University, many courses offer small-group sessions, and students can freely choose these sessions based on their needs. However, the capacity of these small-group sessions is not infinite, so not every student can enroll in their preferred session.

This semester, a total of $n$ students have enrolled in Course A, which offers $m$ small-group sessions. The $i$-th session has a capacity of $b_i$. Each student $i$ has a preference ranking for the sessions, denoted as $a_{i,1} \sim a_{i,m}$, where $a_{i,1}$ is the most preferred session and $a_{i,m}$ is the least preferred. The enrollment process is as follows: students choose their sessions in the order of $1 \sim n$. During each student's turn, they select their most preferred session that has not yet reached its capacity. If all sessions are full, the student will not enroll in any session.

As an assistant, you have access to all students' preferences $a$. You need to process $q$ events, where each event is one of the following two types:

1. A student modifies their preference ranking.
2. You need to answer the following query: Given the capacities of the small-group sessions $b_1 \sim b_m$, what is the remaining capacity of each session after the enrollment process?

Input

The first line contains three positive integers $n, m, q$ ($1 \le n, q < 131072$, $2 \le m \le 5$), representing the number of students, the number of small-group sessions, and the number of events, respectively.

The next $n$ lines each contain $m$ integers, where the $j$-th integer in the $i$-th line is $a_{i,j}$ ($1 \le a_{i, j} \le m$). It is guaranteed that $a_{i, 1} \sim a_{i, m}$ is a permutation of $1 \sim m$.

The next $q$ lines each start with an integer $opt \in \{1, 2\}$, representing the event type:

If $opt = 1$, it is followed by $m + 1$ integers $x, c_1, c_2, \dots, c_m$ ($1 \le x \le n$, $1 \le c_i \le m$), indicating that the preference ranking of student $x$ is changed to $c_1 \sim c_m$. It is guaranteed that $c_1 \sim c_m$ is a permutation of $1 \sim m$.

If $opt = 2$, it is followed by $m$ integers $b_1, b_2, \dots, b_m$ ($0 \le b_i \le n$), representing a query where the capacities of the small-group sessions are $b_1 \sim b_m$.

Output

For each event where $opt = 2$, output a single line containing $m$ integers, where the $i$-th integer represents the remaining capacity of the $i$-th small-group session.

Examples

Input 1

5 3 5
1 2 3
1 2 3
3 2 1
3 1 2
2 1 3
2 3 1 3
2 1 4 1
2 1 4 4
1 2 3 2 1
2 1 4 4

Output 1

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