Facebook Hacker Cup 2019 Final Round

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 $A_i$ and $B_i$. 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 $E_i$ and $V_i$, with $E_i$ indicating the event's type, which is one of the following:

• $E_i=1$: The $V_i$th conduit $(1\le V_i\le M)$ collapses, and can no longer be used from that moment onwards. Each conduit collapses at most once.
• $E_i=2$: The geyser on planet $V_i$ $(1\le V_i\le N)$ activates, and begins emitting neurozine. Each geyser is activated at most once.
• $E_i=3$: The geyser on planet $V_i$ $(1\le V_i\le 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 $X_i$ just before hour $Y_i$. 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 ${\text{ans}}_i$ be the answer for the $i$th starting situation, you must output the sum of ${\text{ans}}_1\dots 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 $X_1\dots S$ and $Y_1\dots S$ explicitly, you must compute them based on given values $X_1^{\prime }\dots S$ and $Y_1^{\prime }\dots S$. For the first starting situation, $X_1=X_1^{\prime }$ and $Y_1=Y_1^{\prime }$, while for each subsequent starting situation $i$ $(2\le i\le S),X_i=X_i^{\prime }{\text{ xor ans}}_{i-1}$ and $Y_i=Y_i^{\prime }{\text{ xor ans}}_{i-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 $A_i$ and $B_i$.

Then, $K$ lines follow, the $i$th of which contains the space-separated integers $E_i$ and $V_i$.

Then, $S$ lines follow, the $i$th of which contains the space-separated integers $X_i^{\prime }$ and $Y_i^{\prime }$.

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\le T\le 100$

$2\le N\le 800000$

$1\le M,K,S\le 800000$

$1\le A_i,B_i\le N$

$1\le E_i\le 3$

$1\le X_i\le N$

$1\le Y_i\le K$

$0\le X_i^{\prime },Y_i^{\prime }\le 1000000000$

The sum of $N$ across all $T$ test cases is no greater than $2000000$.

The sum of $M$ across all $T$ test cases is no greater than $2000000$.

The sum of $K$ across all $T$ test cases is no greater than $2000000$.

The sum of $S$ across all $T$ test cases is no greater than $2000000$.

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

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 $1$st 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 $1$st 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$	$X_i$	$Y_i$	${\text{ans}}_i$
$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$	$X_i$	$Y_i$	${\text{ans}}_i$
$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$	$X_i$	$Y_i$	${\text{ans}}_i$
$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$	$X_i$	$Y_i$	${\text{ans}}_i$
$1$	$20$	$47$	$2$
$2$	$4$	$49$	$7$
$3$	$24$	$47$	$1$
$4$	$20$	$9$	$13$
$5$	$3$	$38$	$9$