CHA - The Chase

no tags 

Original problem statements can be found here: in Polish and in English.

Archibald the Archeologist was dashing forward as fast as he could, clutching The Idol of Ingenuity tightly. Seizing that artifact almost got him killed1, but he still wasn't safe - bunch of South American Indians from Kampa tribe was right on his tail. Fortunately none of them had bows, but they will surely kill him as soon as they catch him. Intricately made figurine was shimmering beautifully in the sun, but at that moment it was only slowing him down - Kampas were faster than him in any case. The situation seemed hopeless...

... but it wasn't. This wasn't a typical jungle - the ground was paved with giant stones, and combined with the surrounding impassable rainforest, it all formed something resembling a corridor. This was surely made by the ancient La-Og-Mhtir civilization, just like the idol. The "corridor" was very long, but very regular - every stone looked like a square, and they were adjoined tightly, one next to the other. Moreover, this corridor was mentioned in the records Archibald studied for years - it surely was The Way Towards Enlightenment. He already expected to find it on his way to the idol, but maybe the map was upside-down...

... anyway, this is good news. Way Towards Enlightenment isn't just a typical road - it contained a lot of deadly traps. There were levers hidden on some of the stones - every such lever activated a trapdoor hidden below the previous stone. Archibald knows exactly where every lever is.

The situation is as follows - Archibald stands on a plate number a. There are n Kampas chasing him, and i-th Kampa is on the xi-th plate. Every Indian moves onto the next plate every second. Archibald is slower - at the start of every second he can decide to move forward, but he will reach the next plate after two seconds. There are m levers, and their positions are denoted by yi. If Archibald reaches one of those levers, he can immediately activate the trapdoor - if there is a Kampa on the plate number yi-1 at this exact moment, he will fall into a deadly trap. Activating the trap earlier is no good - without the element of surprise, the natives will spot it in advance and run through it safely (probably a bit to the side).

The plan is very simple - neutralize all the Indians without getting caught by them.

1 You can find this story in the problem "The Idol", from PIZZA 2017 qualifying round.


The first line contains a single integer t, denoting number of testcases. Then, testcases follow.

The first line of a testcase contains three integers n, m, a ( 1 <= n <= m <= 1000, 0 <= a <= 109 ) - number of Indians, number of traps and Archibald's starting plate.

In the next line there are n integers xi - plate numbers with Kampas on them at the start. In the last line there are m numbers yi - plate numbers with levers.

It is true that:

0 <= x1 < x2 < ... < xn < a

0 < y1 < y2 < ... < ym <= 109


For every testcase you should find a sequence of moves that will let Archibald trap every Indian. The sequence should start with an integer r - number of moves ( 0 <= r <= 16m ). Then you should give a description of the subsequent r moves. Possible moves are as follows:

  • P x - Archibald goes to the right x times. Every move takes him 2 seconds.
  • S x - Archibald stands still for x seconds.
  • X - Archibald activates a trapdoor (this happens instantaneously). There has to be a lever on the plate Archibald is standing on. You cannot activate the same trap more than once.

In every case x is an integer, and x >= 1.

Archibald cannot go to the left, because there is no turning back from The Way of Enlightenment. If at the start of a second Archibald will decide to go to the right, he will still be standing on the same plate at the start of the next second - he will appear on the next plate two seconds after his decision. Indians move at the same time as Archibald - at the start of every second the decide to go right, and at the start of the next second they are at the next plate. At no point should any Kampa stand on the same plate as Archibald. Input is constructed in such a way that a correct sequence always exists.



2 2 8
0 3
12 14


P 4
P 2
S 1


Archibald has to run towards the first lever as fast as he can - after 8 seconds from the start he reaches square number 12, and this is the last possible moment - Kampa closest to him reached plate number 11 already. After he reaches the second trap he has to wait for a second, so the Indian is right above the trapdoor.

Added by:Piotr Jagiełło
Time limit:1s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:PIZZA 2018 qualifying round