Description

Dew-White有很多名言，例如：

“只有巨佬才天天说自己菜”

“我最菜”

一次偶然，他进入了喷射战士的战场

战场由$n*n$的网格组成，每个格子刚开始并没有颜色，用$0$表示,格子有自己的坐标$(a,b)$

DW有3种操作:

操作1:将$（x,y）$染成某个颜色。（用编号代替颜色）

操作2:用$（x_1,y_1）$的颜色给$（x_2,y_2）$染色。（这两个格子之间存在公共边）

操作3:询问$（x,y）$的颜色。

每次染色都会使与其相邻的相同颜色的格子染上颜色，特别的，两个格子都为颜色0不视为相同颜色

现给出他的$m$个操作，请对每一个操作3进行回答。

染色解释：

Input Format

第一行：两个整数$N$（$1 \le N \le 1000$）,$M$（$1 \le M \le 200000$）

接下来M行：每行第一个整数为$type$（$1 \le type \le 3$），表示第$type$种操作，

若$type=1$，则接下来有三个整数,$X,Y,num,(X,Y)$表示格子坐标,$num$表示要染成的颜色。

若$type=2$，则接下来有四个整数,$X_1,Y_1,X_2,Y_2$，表示用$(X_1,Y_1)$的颜色给（X2,Y2）染色。

若$type=3$，则接下来有两个整数,$X,Y$，表示询问$(X,Y)$上的颜色。

Output Format

输出包含若干行，每行一个整数，依次表示询问对应的答案。

Sample

Input:

3 9
1 3 1 2
1 1 3 10
3 3 2
1 3 2 5
3 2 2
2 3 2 3 3
2 3 3 2 3
3 2 3
3 1 3

Output:

0
0
5
10

Hint

对于$20\%$的数据，保证只有操作1和操作3

对于$50\%$的数据，$N \le 10,M \le 1000$

对于所有数据，$N \le 100,M \le 200000,1 \le num \le 10$

注意：不要用y1当变量名

 若出现以下非法情况：坐标为0（例如（0，1））；用颜色为0的格子给其他格子染色。请读入后直接忽略。