Sunny is very rich so he owns a garden that can be considered as a $N \times N$ grid — the top-left corner is $(1, 1)$ and the bottom-right corner is $(N, N)$. In the beginning, each cell is empty. Sunny also has the seeds for $M$ types of plants which he can plant in any cell. The names of the plants are $s_1, \cdots, s_M$.

Sunny will perform $Q$ operations:

1. Grow a plant of type $p$ in cell $(r, c)$. If there is already a plant in this cell, it gets replaced.
2. Count the number of plants of type $p$ in his garden.

You may assume the operations are always valid, i.e. $(r, c)$ is a cell in the garden, and the plant will one of the specified $M$ types.

Input

The first line of input contains three integers $N$, $M$ and $Q$.
The next $M$ lines contain the plants' names $s_1, \cdots, s_M$.
The next $Q$ lines will be of the form 1 p r c (operation type 1) or 2 p (operation type 2).

Output

For each type 2 operation, output the required count on its own line.

Constraints

For all subtasks:
$1 \le M \le 20$
$1\le Q \le 2 \times 10^5$
The plants' names consist of lowercase English letters, with length between 1 and 10.

Subtask 1 (20%): $1 \le N \le 300$
Subtask 2 (80%): $1 \le N \le 10^6$