题目描述

奇葩建筑家 Silly Hook 受雇于某 GFS，在 GFS 耗费巨资买下的郊外一块风水宝地上设计奇葩别墅，但令他震惊的是，一群 DSJ 对 GFS 的富贵生活深恶痛绝，决定打洞以搞破坏。问题描述在上一次的 Challenge 中，DSJ 大获全胜，风水宝地上已是千疮百孔。Silly Hook 只得合理利用资源，用已有的洞作为建筑的基点，同时，他还叫上了他的 J 友 Shabby Hook 来帮助填洞。现在我们简化一下这个问题，初始土地上有 $n$ 个洞（从 $1$ 开始编号），然后在这片土地上会按顺序发生一系列事件。

1. H x d 表示 $x$ 号洞的深度变化了 $d$。如果 $d\le 0$，说明 Shabby Hook 填平了一点这个洞，深度变小或无明显变化。否则就是 DSJ 继续打洞导致深度变大。

2. A m xi 表示 Silly Hook 设计的别墅的地基位置，即由给出的 $m$ 个洞（第 $i$ 个洞的编号为 $x_i$）按顺时针顺序构成的多边形。同时他在设计后想知道当时这个多边形内（包括边界）洞的深度之和以及最大深度。

Silly Hook 和 Shabby Hook 现在对 DSJ 已经忍无可忍了，请你帮他们回答这些询问。

建筑家 Silly Hook 尽管奇葩，但设计的多边形至少还是不会自交的（除相邻边有一个公共点外其他边之间都没有公共点）。

此外，为了降低难度，Silly Hook 保证设计的多边形两两只会在洞处相交，同时所有洞都可以通过多边形的边到达其他的洞（即所有询问组成连通的平面图）。

输入格式

第一行一个整数 $Case$ 表示数据点编号。
接下来一行一个整数 $n$ 表示初始洞的个数。
接下来 $n$ 行，每行三个整数 $x,y,d$，表示坐标为 $(x,y)$ 处有一个深度为 $d$ 的洞。
接下来一行一个整数 $q$ 表示事件的数量。
接下来 $q$ 个事件，每个事件的格式如上所述。

输出格式

对于每个 A 事件输出两个整数表示当时该多边形内的洞的深度之和以及最大深度。

0
6
1 1 1
2 2 1
2 3 1
2 4 1
2 5 1
4 1 1
6
A 3 1 2 6
A 3 1 3 6
A 3 1 4 6
A 3 1 5 6
A 3 1 3 2
A 3 2 3 6

3 1
4 1
5 1
6 1
3 1
3 1

数据规模与约定

对于 $100\%$ 的数据，$n,q\le 5\times 10^4$，$d\le 1.6\times 10^5$，$|x|,|y|\le 10^7$。

题目来源

2014年国家集训队十五人互测 By 佚名提供