infinite XYZ

A directed graph has $N$ vertices and $M$ one-way edges. Several edges may connect the same start and end vertices, and an edge may start and end at the same vertex.

Each edge is labeled with one of $x$, $y$, or $z$. The edges leaving any one vertex have different labels.

The queries are as follows.

• $s$ $e$ $c$: Add a new one-way edge from $s$ to $e$ with label $c$. The new edge may share a label with existing edges. Print 1 if there is a starting vertex from which you can keep moving forever on the graph, otherwise print 0.

Movement follows a fixed rule. After an $x$ edge, you must take a $y$ edge. After a $y$ edge, you must take a $z$ edge. After a $z$ edge, you must take an $x$ edge. In other words, the labels can only follow the pattern $xyzxyz\cdots$, $yzxyzx\cdots$, or $zxyzxy\cdots$.

There are $Q$ queries. Each query is independent, and edges added by an earlier query do not apply to later queries.

The first line contains $N$, $M$, and $Q$ ($1 \leq N \leq 100000$, $1 \leq M \leq 3 \times N$, $1 \leq Q \leq 100000$).

The next $M$ lines each contain $S_i$, $E_i$, and $C_i$, describing an edge from $S_i$ to $E_i$ with label $C_i$ ($1 \leq S_i, E_i \leq N$, $C_i \in \{x,y,z\}$).

The last $Q$ lines each contain a query $s$, $e$, and $c$ ($1 \leq s, e \leq N$, $c \in \{x,y,z\}$).

Print $Q$ lines. On line $i$, print the answer to the $i$-th query: 1 if you can move forever, otherwise 0.