5.沧海桑田

题目描述

有一片海洋，随着时间的推移，逐渐出现了陆地。我们可以用一张$50$行$10^5$列的网格图来描述，其中网格的每一行用$1$~$50$来编号，每一列用$1$~$10^5$来编号，$(x,y)$表示第$x$行第$y$列的网格。

接下来将按时间顺序发生$T$件事件，我们用$opt$ $x_1$ $y_1$ $x_2$ $y_2$来描述：

• $opt=0$，此时$(x_1,y_1)$与$(x_2,y_2)$构成的矩形区域的海洋变为陆地，已经是陆地的网格仍为陆地（不保证$(x_1,y_1)$和$(x_2,y_2)$为矩形的左上角与右下角）。
• $opt=1$，一名可以向上下左右四个方向移动（即只能从$(x,y)$向$(x+1,y)$,$(x-1,y)$,$(x,y+1)$,$(x,y-1)$移动）的旅行家计划从$(x_1,y_1)$到达$(x_2,y_2)$，且路径上的点包括起点和终点都只能经过陆地区域。

你的任务是对于$opt=1$的事件，回答旅行家的计划是否能实现，若能，输出$1$，否则输出$0$。

输入格式

第一行为一个正整数$T$。

接下来$T$行，每行五个正整数$opt$,$x_1$,$y_1$,$x_2$,$y_2$。

输出格式

对于每件$opt=1$的事件，输出一个非负整数，表示答案。

数据范围与提示

• 子任务$1$（$30$分）：$T \leq 10^3$，$1 \leq y_1,y_2 \leq 10^3$；
• 子任务$2$（$70$分）：无特殊限制；
• 对于$100\%$的数据，满足$1 \leq T \leq 2 \times 10^5$，$1 \leq x_1,x_2 \leq 50$，$1 \leq y_1,y_2 \leq 10^5$，$opt \in \{0,1\}$。

样例

6
0 4 4 6 6
0 6 6 7 8
0 1 3 3 3
1 1 7 6 1
1 5 4 6 8
1 4 5 1 3

0
1
0

3
0 1 1 1 1
0 1 2 1 2
1 1 1 1 2

1

见cover3.in

见cover3.out