F. IPs
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Mike just got an internship at the local internet service provider, DNS. Knowing that Mike is familiar with IPs, they have asked him to implement a management system for their clients supporting a few operations. Some of those operations are client specific, while others are DNS (company) specific. Mike doesn't actually know much about IPs, so he has asked for your help.

IPs range from 0 to $$$10^9$$$ and are all initially available to all clients. There are $$$N$$$ countries (numbered from $$$0$$$ to $$$N - 1$$$), each with its own set of IPs modeled as a union of intervals. There are $$$M$$$ clients (numbered from $$$0$$$ to $$$M - 1$$$) Mike needs to help out with and $$$Q$$$ queries to answer. The queries have the following form:

  1. Blacklist a country for all clients. Blacklisting a country blocks all the IPs corresponding to that country and the countries it is merged with.
  2. Blacklist an interval of IPs [$$$X$$$, $$$Y$$$] for all clients.
  3. Blacklist a country for a specific client. Similar to query $$$1$$$, but the impact is limited to one client.
  4. Blacklist an interval of IPs [$$$X$$$, $$$Y$$$] for a specific client.
  5. Whitelist a country for a specific client. Whitelisting a country whitelists all the IPs corresponding to that country and the countries it is merged with. Note that a whitelist takes precedence ahead of any previous or future applicable blacklist for this client.
  6. Whitelist an interval of IPs [$$$X$$$, $$$Y$$$] for a specific client. Note that a whitelist takes precedence ahead of any previous or future applicable blacklist for this client.
  7. Countries $$$X$$$ and $$$Y$$$ are merged together. Note that the merge behavior will only be reflected in new queries. If the countries had previous merges, the whole group of countries will be merged.
  8. How many IPs does a client have access to within an interval [$$$X$$$, $$$Y$$$]?

Since the input and output are quite large, we recommend using fast methods of reading and writing, such as desynchronization in C++.

Input

The first line contains integers $$$N$$$, $$$M$$$, $$$Q$$$. It is guaranteed that $$$1 \leq N \leq 10^4$$$, $$$1 \leq M \leq 10$$$, $$$1 \leq Q \leq 10^5$$$.

On the next $$$N$$$ lines, each line contains an integer $$$N_i$$$ followed by $$$2 \times N_i$$$ integers ($$$X_i^1, Y_i^1, ..., X_i^{N_i}, Y_i^{N_i}$$$) corresponding to $$$N_i$$$ intervals. Each integer is between $$$0$$$ and $$$10^9$$$. The union of these $$$N_i$$$ intervals represents the country's set of IPs. Note that $$$\sum_{i=1}^{N} N_i \leq 10^5$$$.

The next $$$Q$$$ lines describe the queries. Each of them starts with an integer $$$1 \leq type \leq 8$$$ representing the query type followed by a number of integers depending on the query type:

  1. $$$countryIdx$$$, where $$$0 \leq countryIdx \lt N$$$.
  2. $$$X$$$, $$$Y$$$ where $$$0 \leq X \leq Y \leq 10^9$$$.
  3. $$$clientIdx$$$, $$$countryIdx$$$, where $$$0 \leq clientIdx \lt M$$$, $$$0 \leq countryIdx \lt N$$$.
  4. $$$clientIdx$$$, $$$X$$$, $$$Y$$$, where $$$0 \leq clientIdx \lt M$$$, $$$0 \leq X \leq Y \leq 10^9$$$.
  5. $$$clientIdx$$$, $$$countryIdx$$$, where $$$0 \leq clientIdx \lt M$$$, $$$0 \leq countryIdx \lt N$$$.
  6. $$$clientIdx$$$, $$$X$$$, $$$Y$$$, where $$$0 \leq clientIdx \lt M$$$, $$$0 \leq X \leq Y \leq 10^9$$$.
  7. $$$country1Idx$$$, $$$country2Idx$$$, where $$$0 \leq country1Idx \lt N$$$, $$$0 \leq country2Idx \lt N$$$.
  8. $$$clientIdx$$$, $$$X$$$, $$$Y$$$, where $$$0 \leq clientIdx \lt M$$$, $$$0 \leq X \leq Y \leq 10^9$$$.
Output

The output file should contain a line per query type $$$8$$$ representing the total number of visible IPs within that interval for that client.

Example
Input
2 1 12
1 1 100
1 500 1000
8 0 1 1000
1 0
2 800 900
8 0 1 1000
7 0 1
3 0 0
8 0 1 1000
4 0 200 400
8 0 1 1000
5 0 1
6 0 95 499
8 0 1 1000
Output
1000
799
399
198
1000