There is an undirected graph with vertices and no edges initially.

Let's define the weight of the path consisting of edges with indices as .

Notice that a path may not be simple. That is, it can go through the same vertices or the same edges multiple times, and the weight will also be the sum for multiple times if so.

You need to perform operations.

There are types of operations:

: add an edge between  and with weight . 

: delete the edge added in the -th operation.

: If there is a path between and with weight , print . Otherwise, print . Notice that a path may not be simple.

给定一个  个点的无向图，一开始没有边。

对于一条有  条边，且边的编号依次为  的路径，其的长度为 .

注意一条路径不必是简单路径。也就是说，它可以多次经过同一个点或同一条边，在这种情况下计算路径的长度时也会将边的长度累加多次。

你需要执行  次操作。

操作有  种：

: 在  和  之间加了一条长  的边。

: 删除第  次操作添加的边。

: 询问是否存在一条模  余  的从  到  的路径（可以不是简单路径）。如果有，输出 。否则，输出 。

输入描述:

The first line contains  integers  --- the numbers of vertices of the graph, the number of operations in the graph, and the modulo.

Then  lines follow. The -th line contains the -th operation. The format of the operation input is shown above. 

In operations, all tokens are non-negative integers. .

It's guaranteed that in each operation , the  must be an operation of type  and it has not been deleted by another operation .

第一行有  个整数，  。

接下来有  行，每行描述一个操作。

操作格式同题目描述。

题目保证，所有输入的数均为非负整数，且 .

题目保证执行第  种操作时，  对应的操作为第  种，且还未被删。

输出描述:

For each operation of types , output a line containing the answer.

对于每个询问操作，输出一行一个整数表示答案。

10 19 96
1 3 1 48
1 3 2 16
2 2
2 1
1 3 3 24
1 2 2 16
1 2 3 6
1 2 3 48
1 2 2 48
1 1 3 16
1 3 3 48
2 5
3 3 4 16
3 3 3 8
1 2 1 48
2 6
3 3 1 32
2 7
2 8

0
1
1