题目描述

Lora 正在玩一个 Bomberman 变种游戏。

游戏地图是一个大小为 10^9 × 10^9 的网格。每个格子可能为空、放着一个箱子，或者放着一块石头。

地图上共有 N 个箱子和 M 个石头。玩家有无限多个炸弹，炸弹有两种类型：

1. 横向炸弹

放在一个当前为空的格子中后爆炸，火焰会同时向左和向右直线传播。

• 火焰遇到石头时停止并消失；
• 火焰遇到箱子时，该箱子被炸毁，火焰同时停止；
• 被炸毁箱子的格子会变为空地。

2. 纵向炸弹

规则与横向炸弹完全相同，只不过火焰改为向上和向下传播。

炸弹是依次引爆的，即前一个炸弹完全结算后，才会放置下一个炸弹。

保证：

• 任意一个有箱子的格子都不在地图边缘；
• 该箱子的上下左右四个相邻格子一开始都为空。

你的目标是用尽量少的炸弹炸掉所有箱子，并给出一种最优放置方案。

输入格式

第一行一个整数 N，表示箱子数。

接下来 N 行，每行两个整数，表示一个箱子的坐标 (x, y)。

然后一行一个整数 M，表示石头数。

接下来 M 行，每行两个整数，表示一个石头的坐标 (x, y)。

左上角对应第一行第一列。

输出格式

第一行输出一个整数 K，表示炸毁全部箱子所需的最少炸弹数。

接下来 K 行，每行输出三个整数 h x y，表示放置一个炸弹：

• h = 1 表示横向炸弹；
• h = 0 表示纵向炸弹；
• (x, y) 为炸弹放置位置。

要求输出顺序与实际放置顺序一致。若有多种最优方案，输出任意一种即可。

放置炸弹时，该格子必须在当时是空的。

数据范围

• 1 <= N, M <= 4 × 10^5
• 所有坐标均在 [1, 10^9] 范围内

子任务

样例

输入

8
6 2
11 4
2 9
6 7
4 9
6 4
6 9
11 9
2
11 7
8 9

输出

5
1 6 5
1 6 4
0 3 9
1 11 5
1 11 10

说明

一种解释如下：

• 在 (6,5) 放横向炸弹，炸掉 (6,4) 与 (6,7) 的箱子；
• 在 (6,4) 放横向炸弹，炸掉 (6,2) 与 (6,9)；
• 在 (3,9) 放纵向炸弹，炸掉 (2,9) 与 (4,9)；
• 在 (11,5) 放横向炸弹，炸掉 (11,4)；
• 在 (11,10) 放横向炸弹，炸掉 (11,9)。