Gooli is a huge company that owns BB buildings in a hilly area. Five years ago, Gooli built slides that allowed employees to go from one building to another (they are not bidirectional), starting a tradition of building slides between buildings. Currently, SS slides exist.

slide circuits codejam solution

For Solution

Click Here!

Gooli is a huge company that owns BB buildings in a hilly area. Five years ago, Gooli built slides that allowed employees to go from one building to another (they are not bidirectional), starting a tradition of building slides between buildings. Currently, SS slides exist.

Melek is Gooli’s Head of Transportation and a problem-solving enthusiast. She was tasked with keeping the slides enjoyable to use. The idea she came up with was disabling some slides such that only circuits remained. A circuit is a set of two or more buildings b1,b2,...,bkb1,b2,…,bk such that there is exactly one slide enabled from building bibi to building bi+1bi+1, for each ii, and exactly one slide enabled from building bkbk to building b1b1. No other slides from or to any of those buildings should be enabled, to prevent misdirection. A state of the slides is then called fun if each building belongs to exactly one circuit.

Slides in Gooli’s campus are numbered with integers between 1 and SS, inclusive. Melek created a slide controlling console that supports two operations: enable and disable. Both operations receive three parameters rr, and mm and perform the operation on each slide xx such that xrℓ≤x≤r and xx is a multiple of mm. An enable operation is valid only if all affected slides are in a disabled state right before the operation is performed. Similarly, a disable operation is valid only if all affected slides are in an enabled state right before the operation is performed.

The following picture illustrates a possible succession of states and operations. The layout has 33 buildings and 33 slides. Slides are light grey when disabled and dark grey when enabled.

Sample input 1

1. Initial state. All sides are disabled.

Sample input 1 with slides 1 and 2 enabled

2. After enable operation with =1ℓ=1r=2r=2, and m=1m=1.

Sample input 1 with slides 1, 2 and 3 enabled

3. After enable operation with =3ℓ=3r=3r=3, and m=1m=1.

Sample input 1 with slides 1 and 3 enabled

4. After disable operation with =1ℓ=1r=3r=3, and m=2m=2.

Sample input 1 with slide 1 enabled

5. After disable operation with =1ℓ=1r=3r=3, and m=3m=3.

Sample input 1 with slides 1 and 2 enabled

6. After enable operation with =1ℓ=1r=2r=2, and m=2m=2.

Unfortunately, Sult, Melek’s cat, found the console and started performing several valid enable and disable operations. After every console operation performed by Sult, Melek wants to know if the state of the slides can be made fun by enabling exactly one currently disabled slide. Note that Melek does not actually enable this slide.

In the picture above, we can see that after the first, third, and last operations, Melek could enable the only disabled slide and get to a fun state. After the second operation, there are two issues. One issue is that there are no currently disabled slides, so Melek cannot enable any. Additionally, the state is already fun, so even if there were additional disabled slides, enabling anything would result in a not fun state. After the fourth operation, there are two disabled slides, but enabling either would not yield a fun state.

All slides are initially disabled, then Sult performs its operations one at a time. After each of Sult’s operations, determine which disabled slide, if any, Melek can enable to put the slides in a fun state.

Input

The first line of the input gives the number of test cases, TTTT test cases follow. Each test case starts with a line containing three integers BBSS, and NN: the number of buildings, slides, and operations to process, respectively. Then, SS lines follow. The ii⁠-⁠th of these lines contains two integers XiXi and YiYi, indicating that the slide with number ii goes from building XiXi to building YiYi. Finally, NN lines represent the operations. The jj⁠-⁠th of these lines contains a character AjAj and three integers LjLjRjRj, and MjMj, describing the jj⁠-⁠th operation. AjAj describes the type of operation using an uppercase E for enable and an uppercase D for disable. The operation is to be performed on slides with numbers that are simultaneously a multiple of MjMj and between LjLj and RjRj, inclusive.

Output

For each test case, output one line containing Case #xxy1 y2  yNy1 y2 … yN, where xx is the test case number (starting from 1) and yjyj is an uppercase X if there is no way to turn the state of slides created by the first jj console operations into a fun state by enabling exactly one disabled slide. Otherwise, yjyj should be an integer representing that enabling the yjyj⁠-⁠th slide would turn the state created by the first jj console operations into a fun state.

Limits

Memory limit: 1 GB.
1XiB1≤Xi≤B, for all ii.
1YiB1≤Yi≤B, for all ii.
XiYiXi≠Yi, for all ii.
(Xi,Yi)(Xj,Yj)(Xi,Yi)≠(Xj,Yj), for all iji≠j.
AjAj is either uppercase E or uppercase D, for all jj.
1LjRjS1≤Lj≤Rj≤S, for all jj.
1MjS1≤Mj≤S, for all jj.
Each operation is valid.

Test Set 1 (Visible Verdict)

Time limit: 10 seconds.
1T1001≤T≤100.
2B1002≤B≤100.
2S10002≤S≤1000.
1N10001≤N≤1000.

Test Set 2 (Hidden Verdict)

Time limit: 120 seconds.
1T301≤T≤30.
2B3×1042≤B≤3×104.
2S3×1052≤S≤3×105.
1N3×1051≤N≤3×105.

Sample

Sample Input
content_copy
2
3 3 5
1 2
2 3
3 1
E 1 2 1
E 3 3 1
D 1 3 2
D 1 3 3
E 1 2 2
5 8 10
1 5
5 3
4 1
3 2
2 4
2 5
2 1
1 4
E 1 8 2
D 4 8 2
E 3 5 1
E 1 1 3
E 1 1 1
E 5 8 2
D 1 8 3
D 5 8 4
D 4 5 1
E 3 4 1
Sample Output
content_copy
Case #1: 3 X 2 X 3
Case #2: 3 X 1 1 X X X 3 X 5

Sample Case #1 is the one depicted in the problem statement.

The following picture shows the building and slide layout of Sample Case #2.

Sample input 2

The sets of enabled slides after each operation are:

  • {2,4,6,8}{2,4,6,8},
  • {2}{2},
  • {2,3,4,5}{2,3,4,5},
  • {2,3,4,5}{2,3,4,5},
  • {1,2,3,4,5}{1,2,3,4,5},
  • {1,2,3,4,5,6,8}{1,2,3,4,5,6,8},
  • {1,2,4,5,8}{1,2,4,5,8},
  • {1,2,4,5}{1,2,4,5},
  • {1,2}{1,2}, and
  • {1,2,3,4}{1,2,3,4}.

    For Solution

    Click Here!

Leave a Comment

Your email address will not be published.