Problem: temporal_revision (2019 finals)

The starship Enterprise, bravely captained by Jean-Luc Picard, is on yet
another mission to explore strange new worlds, seek out new life and new
civilizations, and boldly go where no one has gone before! Equipped with a
state-of-the-art warp drive capable of attaining warp factor 11 and revising
the Enterprise's space-time coordinates almost at will (even sending the ship
back in time), not much can stand in the explorers' way. Though, they _are_
low on medical supplies, so they will need to first stock up on neurozine gas
for anesthetic purposes.

The Enterprise is heading to the Alpha Omicron solar system, which consists of
**N** planets, numbered from 1 to **N**. It also features **M** space
conduits, the _i_th of which allows the Enterprise to travel in either
direction between two different planets **Ai** and **Bi**. No two conduits
directly link the same unordered pair of planets, and **each planet is
reachable from each other planet** by following a sequence of conduits.

There's a geyser capable of emitting neurozine located on each planet, though
all **N** geysers are initially inactive. A sequence of **K** events will then
take place, one per hour. The event at hour _i_ is described by integers
**Ei** and **Vi**, with **Ei** indicating the event's type, which is one of
the following:

  * **Ei** = 1: The **Vi**th conduit (1 ≤ **Vi** ≤ **M**) collapses, and can no longer be used from that moment onwards. Each conduit collapses at most once. 
  * **Ei** = 2: The geyser on planet **Vi** (1 ≤ **Vi** ≤ **N**) activates, and begins emitting neurozine. Each geyser is activated at most once. 
  * **Ei** = 3: The geyser on planet **Vi** (1 ≤ **Vi** ≤ **N**) deactivates, and no longer emits neurozine from that moment onwards. Each geyser is deactivated at most once, and is guaranteed to not be deactivated before it has been activated. 

The Enterprise will arrive in the Alpha Omicron system at some planet _x_ and
just before some hour _y_. When the starship is currently at a certain planet
(and a certain time), Captain Picard may issue any of the following commands
to his crew:

  * Remain at that planet and wait until any future time. 
  * Travel through an uncollapsed space conduit directly from that planet to another one. Thanks to warp technology, this may be done instantly. 
  * Collect neurozine from that planet's geyser, if it's currently active. This may be done instantly. 
  * Remain at that planet while travelling backwards to any past time which is **at most 24 hours earlier than the Enterprise's original arrival time in the solar system** (in other words, the Enterprise may end up just before hour (_y_ \- 24), but no earlier). However, **this may only be done at most once**. The Enterprise retains any neurozine that it had collected before this "temporal revision". 

Picard wants his crew to collect neurozine from as many _different_ geysers as
possible; there's no additional value in collecting neurozine from any given
geyser multiple times, including both before and after travelling back in
time. However, Picard hasn't yet decided where and when the Enterprise should
arrive in the Alpha Omicron system. He has **S** such possible starting
situations in mind, the _i_th of which would have the Enterprise arrive at
planet **Xi** just before hour **Yi**. For each hypothetical starting
situation, please help Picard determine the maximum number of different
geysers from which the Enterprise could then proceed to collect neurozine!

Letting **ansi** be the answer for the _i_th starting situation, you must
output the sum of **ans1..S** in order to minimize the size of the output.
Please note that this sum may not fit within a 32-bit integer.

The starting situations must be considered one after another. In order to
enforce this, rather than being given **X1..S** and **Y1..S** explicitly, you
must compute them based on given values **X'1..S** and **Y'1..S**. For the
first starting situation, **X1** = **X'1** and **Y1** = **Y'1**, while for
each subsequent starting situation _i_ (2 ≤ _i_ ≤ **S**), **Xi** = **X'i** xor
**ansi-1** and **Yi** = **Y'i** xor **ansi-1** (where "xor" is the bitwise xor
operator, "^" in most programming languages).

### Input

Input begins with an integer **T**, the number of missions.  
For each mission, there is first a line containing the space-separated
integers **N**, **M**, **K** and **S**.  
Then, **M** lines follow, the _i_th of which contains the space-separated
integers **Ai** and **Bi**.  
Then, **K** lines follow, the _i_th of which contains the space-separated
integers **Ei** and **Vi**.  
Then, **S** lines follow, the _i_th of which contains the space-separated
integers **X'i** and **Y'i**.

### Output

For the _i_th mission, print a line containing "Case #_i_: " followed by one
integer, the sum of the answers for the **S** starting situations.

### Constraints

1 ≤ **T** ≤ 100  
2 ≤ **N** ≤ 800,000  
1 ≤ **M**, **K**, **S** ≤ 800,000  
1 ≤ **Ai**, **Bi** ≤ **N**  
1 ≤ **Ei** ≤ 3  
1 ≤ **Xi** ≤ **N**  
1 ≤ **Yi** ≤ **K**  
0 ≤ **X'i**, **Y'i** ≤ 1,000,000,000  

The sum of **N** across all **T** test cases is no greater than 2,000,000.  
The sum of **M** across all **T** test cases is no greater than 2,000,000.  
The sum of **K** across all **T** test cases is no greater than 2,000,000.  
The sum of **S** across all **T** test cases is no greater than 2,000,000.

### Explanation of Sample

In the first case, if the Enterprise arrives at planet 1 just before hour 3,
Picard could issue the following sequence of orders to help his crew collect
neurozine from both planets' geysers:

  1. Travel through the 1st space conduit to planet 2. 
  2. Wait until after hour 3. 
  3. Collect neurozine from planet 2's now-active geyser. 
  4. Travel back in time to just before hour 2. 
  5. Travel through the 1st space conduit to planet 1. 
  6. Collected neurozine from planet 1's active geyser. 

In the second case, the starting situations and corresponding answers are as
follows:

      i | Xi | Yi | ansi
      ------------------
      1 |  2 |  1 |    3
      2 |  1 |  6 |    2
      3 |  3 |  5 |    3

For the first starting situation, the Enterprise could remain on planet 2
until its geyser activates at hour 6, collect its neurozine, travel back in
time to just before hour 2, travel to planet 1 and collect its neurozine,
travel to planet 2 and then to planet 3, and remain there to collect its
neurozine after hour 5. On the other hand, for the second starting situation,
neurozine from all 3 geysers cannot be collected.

In the third case, the starting situations and corresponding answers are as
follows:

      i | Xi | Yi | ansi
      ------------------
      1 |  1 |  4 |    4
      2 |  5 |  8 |    3
      3 |  2 |  9 |    3
      4 |  3 |  6 |    4

In the fourth case, the starting situations and corresponding answers are as
follows:

      i | Xi | Yi | ansi
      ------------------
      1 |  6 | 16 |    7
      2 |  4 |  6 |    8
      3 | 10 | 22 |    7
      4 |  3 | 13 |    7
      5 |  6 | 11 |    8
      6 |  5 | 17 |    6
      7 |  2 | 21 |    7

In the fifth case, the first 5 starting situations and corresponding answers
are as follows:

      i | Xi | Yi | ansi
      ------------------
      1 | 20 | 47 |    2
      2 |  4 | 49 |    7
      3 | 24 | 47 |    1
      4 | 20 |  9 |   13
      5 |  3 | 38 |    9



Sample input:
5
2 1 3 1
1 2
2 1
3 1
2 2
1 3
3 2 6 3
1 2
2 3
2 1
1 2
3 1
1 1
2 3
2 2
2 1
2 5
1 7
5 6 9 4
1 2
2 3
3 4
4 5
5 1
4 2
1 2
2 2
1 6
1 4
2 3
2 1
1 5
3 1
2 5
1 4
1 12
1 10
0 5
10 12 23 7
2 4
6 5
6 7
6 9
4 1
4 6
8 10
8 2
9 1
3 6
5 2
5 1
2 4
1 11
2 9
1 4
2 8
3 9
1 1
2 6
1 12
3 4
2 7
1 10
2 2
2 3
3 7
1 6
2 1
1 2
3 3
3 2
1 7
3 1
2 10
6 16
3 1
2 30
4 10
1 12
13 25
4 19
25 28 50 30
14 4
8 19
19 24
1 8
16 2
22 10
16 11
9 14
23 1
9 10
17 12
22 12
16 7
1 14
12 18
15 13
6 8
7 3
25 2
5 11
20 16
21 14
7 24
2 13
14 7
9 16
4 11
23 6
2 18
1 5
1 19
2 15
1 6
2 3
2 17
1 3
1 7
2 5
2 4
2 8
2 14
1 23
1 20
1 25
2 9
3 15
2 12
1 15
1 26
1 17
2 1
2 24
1 24
3 5
3 24
1 13
1 12
2 16
1 27
2 21
1 4
3 16
3 18
2 25
1 28
1 18
1 9
2 22
2 6
2 19
2 10
2 13
3 9
3 25
3 10
3 14
3 19
2 2
20 47
6 51
31 40
21 8
14 43
4 35
27 7
30 4
21 41
26 57
31 46
24 45
20 26
27 17
10 44
3 20
15 9
1 0
25 37
25 37
20 40
17 44
19 30
9 26
7 8
0 63
7 39
1 41
8 12
5 31


Sample output:
Case #1: 2
Case #2: 8
Case #3: 14
Case #4: 50
Case #5: 246