平面上有 $n$ 个圆盘。这些圆盘的半径可以不同。圆盘之间互不相交，也不相切。圆盘的边界包含在其区域内。你的任务是绘制 $n-1$ 条直线段来连接这些圆盘，使得任意两个圆盘之间都存在一条路径，且该路径仅在圆盘区域内或直线段上行走。

关于这些直线段，有以下限制：

• 直线段的端点坐标必须为整数。
• 一条直线段最多只能接触或穿过两个圆盘。
• 任意两条直线段不能相交，也不能接触。唯一的例外是允许两条直线段共享一个端点。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 200\,000$)，表示圆盘的数量。

接下来的 $n$ 行，每行包含三个整数 $x_i, y_i$ 和 $r_i$ ($0 \le x_i, y_i \le 10^9, 1 \le r_i \le 10^9$)，分别表示圆心坐标为 $(x_i, y_i)$ 且半径为 $r_i$ 的圆盘。

保证任意两个圆盘互不相交或相切。

输出格式

如果存在满足条件的方案，输出 “YES”，否则输出 “NO”。如果答案为 “YES”，则在接下来的行中输出直线段的描述。

描述包含 $n-1$ 行。每行包含 4 个整数 $x_1, y_1, x_2, y_2$，表示连接点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的直线段。这两个点不能相同。此外，必须满足 $0 \le x_1, y_1, x_2, y_2 \le 10^9$。可以证明，如果存在解，则一定存在满足该坐标范围的解。

样例

样例输入 1

3
1 0 3
10 10 6
0 5 1

样例输出 1

YES
0 4 7 12
0 0 16 8

样例输入 2

2
1 1 1
3 3 1

样例输出 2

YES
2 1 3 2

样例输入 3

5
10 10 10
2 0 1
20 20 1
3 20 1
20 0 1

样例输出 3

YES
1 0 10 10
20 0 10 10
20 10 20 22
3 20 10 10

说明

样例 3 可视化