Problem Statement

There are $N$ colorful cities connected by $M$ roads. The $i$-th road connects cities $u_i,v_i$, and the cities as a whole can be regarded as a simple undirected graph (not necessarily connected).

Each city has zero or more of the colors 1 to 7. The colors that city $i$ has are represented by a 01 string $s_i$ of length 7, where the $i$-th character from the left indicates whether the city has color $i$. For example, $0100110$ means that the city has colors 2, 5, and 6. Colors may also be added later.

Momohara-san has decided to go on a trip starting from some city.
Since Momohara-san is gaming-spec, she can change among seven colors. She is initially pink (color 1), but while in any city, she can increase or decrease her color by 1 at any time she likes. Color 0 is regarded as color 7, and color 8 is regarded as color 1.

A trip consists of performing the following operations 1 and 2 any number of times in any order, and then performing operation 3 exactly once.
1. Move to a city directly connected by a road to the current city.
2. Stay in the current city and change her color by one step.
3. Take a selfie. The photo taken is represented by the pair (current city, her current color).

However, for the sake of appearance, at no moment during the operations may the current city lack Momohara-san's current color.

Regarding such trips, process a total of $Q$ queries of the following two types.

• $1 \ x \ y$

• Add color $y$ to city $x$. It is guaranteed that city $x$ does not have color $y$ at this time.

• $2 \ x \ 0$

• When starting a trip from city $x$, output the number of distinct selfie photos that are possible. It is guaranteed that city $x$ has color 1 at this time.

Input

$N\ M\ Q$
$s_1$
$\vdots$
$s_N$
$u_1\ v_1$
$\vdots$
$u_M\ v_M$
$Query_1$
$\vdots$
$Query_Q$

• All inputs are integers
• The given graph is a simple graph
• $1 \leq N,Q \leq 10^5$
• $0 \leq M \leq 10^5$
• $s_i$ is a 01 string of length 7
• $1 \leq u_i < v_i \leq N$
• For query 1, $1 \leq x \leq N,\ 1 \leq y \leq 7$, and city $x$ does not have color $y$
• For query 2, $1 \leq x \leq N$, and city $x$ has color 1
• There is at least one query 2

Output

Output the answers to query 2, separated by newlines.

Sample

Sample 1

Input

3 2 3
1010000
1000000
0010000
1 2
1 3
2 1 0
1 1 2
2 1 0

Output

2
5

In the 1st query, a trip starts from city 1.
In the 2nd query, color 2 is added to city 1.
In the 3rd query, a trip starts from city 1.

The states of the cities at the time of the 1st query and the 3rd query are shown in the figures below, respectively. (Colors 1, 2, and 3 are represented by pink, yellow, and green, respectively.)

1 0 1
1000001
2 1 0

2

7 7 7
1100100
1011000
1001000
1100111
1001110
1010110
1100100
3 4
2 6
2 5
3 6
3 7
1 3
4 5
2 3 0
1 3 5
2 5 0
2 7 0
1 4 4
1 4 3
2 4 0

19
25
25
27