题目描述

译自 CERC 2018「G. Shooter Island」

你最近被提拔成上尉，现在你正带着你的士兵在暴风雪中执行一项特别任务。战场有点特别，因为它位于北极圈内的一个巨型冰盖上。你需要和总部协调行动。总部有很多高端的计算机协助你获得战场的最新状态。AI 接口将战场建模为一个网格。每个单元格被它所处行列号唯一确定。由单元格组成的大一些的矩形用对角线顶点的单元格对表示。最初，所有单元格被冰覆盖。

你可以从计算机端接收到两种信息：

0. 关于打击的信息（$t=0$）：你的敌人打击了被单元格 $[x_1,y_1]$ 和 $[x_2,y_2]$ 描述的矩形区域，然后这个矩形区域就被冰冷的北冰洋海水淹没了；
1. 来自你士兵的询问（$t=1$）：他们问是否可以乘船从 $[x_1,y_1]$ 航行到 $[x_2,y_2]$。这条船可以用一个半径为 $0.31416$ 的圆表示。注意船体全部必须一直浮在水上，并且它不能离开战场区域。

你的士兵需要你的帮助！你能可靠地引导他们完成任务吗？

输入格式

输入第一行包含一个整数 $L$，表示接下来的行数。

接下来 $L$ 行，每行五个整数 $t,x_1,y_1,x_2,y_2$，$t$ 是信息的类型，$[x_1,y_1],[x_2,y_2]$ 表示各自的单元格。

输出格式

对于每个查询，如果可以从 $[x_1,y_1]$ 乘船到达 $[x_2,y_2]$，则输出 $1$，否则输出 $0$。

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

数据范围与提示

$1\le L\le 2\times 10^5,t\in \{0,1\},1\le x_1,x_2\le 50,1\le y_1,y_2\le 10^5$