MSS

内存限制：512 MiB 时间限制：30 Sec

　小C正在出一道题...因为语文水平有限他想不出复杂的背景，所以以下就是题意了。
　　平面上有N个点，开始时每个点属于一个不同的集合。不妨设点P_i属于集合S_i。请维护数据结构支持以下三种操作：
　　"Merge x y"：将集合S_y中的点到S_x中；
　　"Split i d v"（d ∈ {0, 1}）：创建新集合S_c + 1，S_c + 2，之后将集合S_i中的所有点中，第d维坐标不超过v的到集合S_c + 1中，超过v的移动到集合S_c + 2中，其中c为现有集合数（包括之前合并和分割中产生的空集）；
　　"Query i"：查询集合S_i中点权值的最大值，最小值及和；
　　"Add i d"：将集合S_i中所有点的权值增加d。
　　方便起见，对于d ∈ {0, 1}，输入的所有点的第d维坐标不重复。所有操作涉及的集合非空。

　　第一行一个整数N表示点数。
　　接下来N行，每行3个整数分别表示P_i的坐标与权值。
　　接下来一个整数Q表示操作数。
　　接下来Q行，每行描述一个操作，格式如上所述。

　　对于每个Q操作，输出三个整数，依次表示询问集合权值的最大值，最小值与和。

样例输入


			5

4 7 3

18 16 2

14 13 1

10 2 10

3 8 5

11

Merge 2 3

Merge 4 5

Split 2 1 13

Query 4

Query 6

Add 6 2

Query 6

Merge 6 4

Split 6 0 10

Query 9

Split 8 0 3

样例输出

N<=50000

Q<=100000

#3615. MSS

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示