무한 XYZ

정점 $N$개와 단방향 간선 $M$개로 이루어진 유향 그래프가 있다. 같은 출발점과 도착점 사이에 간선이 여러 개 있을 수 있으며, 간선의 출발점과 도착점이 같을 수도 있다.

각 간선에는 $x$, $y$, $z$ 중 하나의 문자가 쓰여 있다. 한 정점에서 뻗어 나가는 간선들의 문자는 서로 겹치지 않는다.

다음과 같은 쿼리가 주어진다.

• $s$ $e$ $c$: 출발점이 $s$이고 도착점이 $e$이며 문자가 $c$인 단방향 간선을 그래프에 새로 추가한다. 새 간선의 문자는 기존 간선과 겹칠 수 있다. 이때, 어떤 정점에서 출발해 그래프 위를 무한히 이동할 수 있으면 1, 그렇지 않으면 0을 출력한다.

이동에는 특별한 규칙이 있다. $x$ 간선 다음에는 $y$ 간선, $y$ 간선 다음에는 $z$ 간선, $z$ 간선 다음에는 $x$ 간선을 타고 이동해야 한다. 즉, 문자 순서는 $xyzxyz\cdots$, $yzxyzx\cdots$, $zxyzxy\cdots$ 중 하나의 형태로만 이어질 수 있다.

쿼리는 $Q$개 주어진다. 각 쿼리는 독립적이며, 앞선 쿼리에서 추가된 간선은 뒤의 쿼리에 적용되지 않는다.

첫 번째 줄에 $N$, $M$, $Q$가 주어진다. ($1 \leq N \leq 100000$, $1 \leq M \leq 3 \times N$, $1 \leq Q \leq 100000$)

둘째 줄부터 $M + 1$번째 줄까지 간선 정보 $S_i$, $E_i$, $C_i$가 주어진다. 이는 $S_i$에서 $E_i$로 가는, 문자 $C_i$가 쓰인 간선을 뜻한다. ($1 \leq S_i, E_i \leq N$, $C_i \in \{x,y,z\}$)

$M + 2$번째 줄부터 $M + Q + 1$번째 줄까지 쿼리 정보 $s$, $e$, $c$가 주어진다. ($1 \leq s, e \leq N$, $c \in \{x,y,z\}$)

$Q$줄에 걸쳐 $i$번째 줄에 $i$번째 쿼리의 답을 출력한다. 무한히 이동할 수 있으면 1, 그렇지 않으면 0을 출력한다.