ACM-ICPC Indonesia National Contest 2014

Problem H

Kawal Pemilu

Time Limit: 2 seconds

You were on vacation and had been following a very intense political news about the presidential election. There are two candidates fighting for presidential chair. You voted on the election day and eagerly following the quick count results. At the end of the day, the unofficial quick count result was tight and both candidates claimed victory, raising fears of political instability.

You discovered (from the newsfeed of a social networking site) that the general elections commission made the scan of C1 forms (i.e., documents that contain the aggregated votes for each polling station) available publicly through its website. You figured that if you can digitize the votes on all of those documents, you will be able to do the recapitulation yourself. However, you could not find any handwriting recognition software that were good enough. After discussing with your friends, it’s decided that crowdsourcing is the way to go. You are going to build a crowdsourcing platform that will later known to be "Kawal Pemilu".

The most challenging part of the crowdsourcing system is the database backend. The database backend needs to be fast enough to handle newly incoming data and display the aggregate votes on any 5 levels of administrative divisions (or also called as "region" in this problem): 0 = national, 1 = province, 2 = regency, 3 = sub-district, 4 = village. Each administrative region of level k is located within exactly one administrative region of level k-1. Obviously there is only one administrative region at level 0, i.e. national region. This problem focuses on this most challenging part.


The input consists of two sections. The first section describes the administrative regions, while the second section lists the queries.

The first section begins with an integer M (1 ≤ M ≤ 8,000) denoting the number of regions in the dataset excluding village level. The following M lines each contains the description of one administrative region (which is not a village), formatted as:

P N C1 C2 ... CN


All regions identifier are non-negative integer less than 106 and unique. You are also guaranteed that:

The second section begins with an integer Q (1 ≤ Q ≤ 600,000) denoting the number of queries received by the system. The next Q lines each contains the actual queries. There are two types of query formatted as follows:


For each query of the second type, output the current total of the aggregated votes for the first and second candidate (in one line) in all villages within the specified administrative region in one line. You are guaranteed that the total of the aggregated votes for both candidates in national level at any time will always fit in signed 32-bit integer.

Warning: Large input and output file. You might want to avoid slow input/output methods.

Sample InputOutput for Sample Input
0 1 1
1 2 2 3
2 3 4 5 6
3 1 7
4 2 8 9
5 1 10
6 1 11
7 1 12
8 11 91
-1 8
8 1 3
-1 4
9 29 8
12 7 3
-1 2
-1 0
10 4 9
12 2 3
8 7 9
-1 6
-1 2
-1 7
-1 0
11 91
12 94
41 102
48 105
0 0
52 120
9 6
61 126

Explanation for the sample input.

The following is the administrative area division:

For example, village 11 is located within sub-district 6, which is located within regency 2, which is located within province 1.