問題文

$N$ 個のカラフルな都市があり、 $M$ 本の道路で結ばれています。 $i$ 番目の道路は都市 $u_i,v_i$ を結び、都市全体は単純無向グラフ（連結とは限らない）と見なせます。

それぞれの都市は色1〜7のうちの0個以上を持ちます。都市 $i$ がどの色を持つかは長さ7の01文字列 $s_i$ で表され、左から $i$ 番目の文字と色 $i$ の有無が対応しています。 例えば $0100110$ ならその都市は色2, 5, 6を持ちます。また、後で色が追加されることもあります。

ももはらさんは、適当な都市から旅行をすることにしました。
ももはらさんはゲーミング仕様なので、七色に変色することができます。 はじめは桃色（色1）ですが、いずれかの都市にいる好きなタイミングで色を1大きくor小さくできます。 また、色0は色7、色8は色1と見なします。

旅行とは、次の操作1, 2を任意の順に任意の回数行った後、操作3をちょうど1回行うことを表します。
1. 現在いる都市と直接道路で繋がれている都市に移動する。
2. 現在いる都市に留まり、色を1段階変色する。
3. 自撮りを行う。このとき撮った写真は（現在の都市、現在の自身の色）のペアで表される。

ただし見栄えの問題があるので、操作のいかなる瞬間においても、現在いる都市が現在のももはらさんの色を持たない状況があってはいけません。

このような旅行に関して、次の2種類のクエリを合計で $Q$ 個処理してください。

• $1xy$

• 都市 $x$ に色 $y$ を追加する。このとき都市 $x$ は色 $y$ を持たないことが保証される。

• $2x0$

• 都市 $x$ から旅行を始めるとき、自撮り写真として有り得るものの種類数を出力する。このとき都市 $x$ は色1を持つことが保証される。

入力

$NMQ$
$s_1$
$⋮$
$s_N$
$u_1{v}_1$
$⋮$
$u_M{v}_M$
$Quer{y}_1$
$⋮$
$Quer{y}_Q$

• 入力は全て整数
• 与えられるグラフは単純グラフである
• $1\le N,Q\le {10}^5$
• $0\le M\le {10}^5$
• $s_i$ は長さ7の01文字列
• $1\le u_i<v_i\le N$
• クエリ1のとき、 $1\le x\le N,1\le y\le 7$ 、都市 $x$ は色 $y$ を持たない
• クエリ2のとき、 $1\le x\le N$ 、都市 $x$ は色1を持つ
• クエリ2は少なくとも1つ存在する

出力

クエリ2に対する解を改行区切りで出力してください。

サンプル

サンプル1

入力サンプルをコピー

入力

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

出力

2
5

1個目のクエリでは、都市1から旅行を始めます。
2番目のクエリでは、都市1に色2を追加します。
3個目のクエリでは、都市1から旅行を始めます。

1番目のクエリ、3番目のクエリ時点での都市の様子はそれぞれ次図のようになります。（色1, 2, 3をそれぞれピンク、黄、緑で表します）

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