2020 UP ACM Algolympics Final Round
A. The Slowden Files
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You, Jacob Slowden, have been hired by the Children of Immortal Agents (CIA) to put a wrench into the Not So Advanced's (NSA's) operations.

Working at the pace of a wolf, which is ironically not that fast—only once every full moon—you go ahead and break into the NSA's system to slow them down. After all, if you are slow, then your enemies must be slowed down as well, keeping your name true to its meaning.

As the NSA was not very advanced, it was very easy for you to gain access to their system. Of course, this does not necessarily mean that you were able to do it fast. In any case, you were still surprised with what you saw. Unencrypted passwords. Basic network configuration. Even Ronald Gump's Tweeter had better security.

Their passwords were already unencrypted, so what else could you do? After thinking for a while, you decided on swapping the passwords between all of their user accounts.

Of course, it wouldn't be good if they suddenly got completely locked out of their account. Even they would be suspicious if that happened. So whenever they try to log in, you give a hint saying how close they are from the correct password. Specifically, you measure this in terms of how many "moves" it would take to turn it into the correct password: one addition, deletion, or replacement of one character counts as one "move". You seem to recall from your Cryptographic Secrets training that this was called the Leviathan distance or something. Or wait, was that a character from the game Decryption of the Aged?

After thinking about how to do this, you now go on to implement your hints:

  • If the entered password matches the correct password, print "You're logged in!"
  • If they are only one move apart, print "You almost got it. You're wrong in just one spot."
  • If it takes exactly two moves, print "You almost got it, but you're wrong in two spots."
  • If it takes exactly three moves, print "You're wrong in three spots."
  • Otherwise, print "What you entered is too different from the real password."

Note that passwords may contain spaces, and passwords are case-sensitive and space-sensitive.

Input

The first line of input starts with an integer $$$t$$$, the number of test cases.

Each test case consists of two lines.

The first line of each test case consists of a single string containing the entered password.

The second line of each test case consists of a single string containing the correct password.

Constraints

  • $$$1 \le t \le 10^4$$$
  • Each password string is nonempty.
  • Each password string consists of characters whose ASCII values are between 33 and 126.
  • Each password string is at most $$$10^5$$$ characters in length.
  • The total length of all strings in the input is $$$\le 2\cdot 10^6$$$.
Output

For each test case, output a single line containing (without the quotes)

  • " You're logged in!" if the entered password matches the correct password;
  • " You almost got it. You're wrong in just one spot." if they are only one move apart;
  • " You almost got it, but you're wrong in two spots." if it takes exactly two moves;
  • " You're wrong in three spots." if it takes exactly three moves;
  • " What you entered is too different from the real password." otherwise.
Example
Input
5
password
password
password
passw0rd
password
pazzword
password
pazzw0rd
password
username
Output
You're logged in!
You almost got it. You're wrong in just one spot.
You almost got it, but you're wrong in two spots.
You're wrong in three spots.
What you entered is too different from the real password.

B. C.U.P.S.
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Taal is erupting; panic ensues, hundreds are fleeing, horses are burning, and another island is forming in the lake (Yellow Lake) inside the island (Volcano Island) inside the lake (Taal Lake) inside the island (Luzon). It looks like the world is ending, but you are unfazed through the crisis. You have no reason to worry, being part of the Craters of Utmost Precedence Society (C.U.P.S) - citizens studying interesting volcano craters since time immemorial. With that, a plan to stop the eruption forms!

Taal threatens to devour Batangas and turn all its citizens into Pompeii and Herculaneum, but with your trusty C.U.P.S. standard issue handbook you figure out that there are $$$n$$$ craters from which lava is flowing from. If left unchecked, these craters will erupt in (also) $$$n$$$ days. Each of the $$$n$$$ craters have one of two states:

  • Completely filled with ash (blocked and stable)
  • Open and spewing with lava (fiery death abound)

A quick survey of the area gives you the state of each of the $$$n$$$ craters $$$S$$$, with $$$S_i$$$ denoting whether the crater is open or not. The cataclysm threatened by Taal will be neutralized if and only if all craters have been completely filled with ash after at most $$$n$$$ days.

To completely fill the craters, your faithful dog (and best friend - because dog is man's best friend <3) Roro can piss on the craters, turning the lava into ash. To this effect you choose $$$m$$$ craters each day for Roro to visit, which can be different or same every day. However, you realize that he's not the brightest of the bunch: he misinterprets your long-term actions into short-term gains, and will always visit exactly $$$m$$$ (no more, no less) craters each day, even if that crater has already been filled with ash. To make matters worse, Taal's volcanic ash is the main component of Roro's favorite food ashbu! If he arrives at a crater currently filled with ash, he will devour the ash inside the crater, opening it again!

Now, you have to plan your actions properly. Given $$$n$$$, the number of craters to completely fill up and consequently the number of days we have, the number of craters $$$m$$$ Roro visits each day, and the inital state of the craters $$$S$$$, find the commands that completely fills Taal volcano if it is even possible, within $$$n$$$ days, or if it is impossible, say so.

Input

The first line of input contains integer $$$t$$$, the number of test cases. $$$t$$$ test cases follow.

Each test case is composed of two lines. The first line contains two space-separated integers $$$n$$$ and $$$m$$$:

  • $$$n$$$: The number of craters in Taal to fill up (and number of days before Taal turns Batangas into a wasteland)
  • $$$m$$$: The number of craters Roro will visit each day.

The second line of a test case contains the initial state of each crater $$$S$$$. $$$S$$$ is represented as a binary string, with $$$S_i$$$ either being $$$0$$$ or $$$1$$$:

  • $$$S_i = 0$$$: The $$$i$$$th crater is open. Close it!
  • $$$S_i = 1$$$: The $$$i$$$th crater is closed. Keep it that way!

Constraints

  • $$$1 \le t \le 2500$$$
  • $$$1 \le m \le n \le 80$$$
Output

For each test case, do the following:

If it is impossible to stop Taal, output the following exact string in a single line:

"CATACLYSM IMMINENT - TIME TO HOARD FACE MASKS"

(without the quotes).

If there is a way to stop Taal, output the craters Roro needs to visit each day in the following format:

  • A line containing the nonnegative integer $$$c$$$ denoting the number of days you and Roro need to stop Taal;
  • $$$c$$$ lines, each containing a binary string $$$t$$$: $$$t_i = 1$$$ means Roro visits crater $$$i$$$, and $$$t_i = 0$$$ otherwise.

There may be multiple possible ways to stop Taal within $$$n$$$ days. In that case, output any of the valid solutions.

Example
Input
1
4 2
1100
Output
3
1100
0011
1100
Note

In the first test case, Taal starts with the first two craters open: 1100. We have to find a way to fill all of these craters in at most $$$4$$$ days, choosing $$$2$$$ craters each day. We achieve this by choosing the first two craters on the first day, last two craters on the second day, and the first two craters (again) at the third day. By the end of the third day, all craters will be filled up:

  1. 0000 after the first day;
  2. 0011 after the second day;
  3. 1111 after the third day.

C. Senpai
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Valentine's Day was just around the corner, but Kouhai still hasn't confessed to Senpai at the Academy of Covert Machinations (ACM)! But alas, Kouhai knows that even if they do confess, it's all for nothing as Senpai has a track record of rejecting every single guy that confesses to her.

Senpai evaluates potential suitors using $$$q$$$ qualities. These qualities are also weighted with $$$W$$$ (where $$$W_i$$$ is the multiplier for the $$$i$$$th quality). Your quality scores is denoted by $$$P$$$, where $$$P_i$$$ is your score for the $$$i$$$th quality. For example, if the your score for quality $$$P_1$$$ is $$$3$$$, and it is weighted with $$$W_1 = 3$$$, your effective quality score is $$$3\times 3 = 9$$$. Obviously, a bigger quality score is better. Likewise, a smaller (or even negative) quality score hurts chances of getting Senpai to notice you.

Likewise Senpai has her own quality scores $$$S$$$, where $$$S_i$$$ is the score for the $$$i$$$th quality. You want to compare this with your own quality scores $$$P$$$. If $$$$$$\sum_{i=1}^{q} S_i \leq \sum_{i=1}^{q} P_i\cdot W_i$$$$$$ (i.e. your total sum of weighted qualities are at least the same as Senpai's), Senpai is then impressed and will accept your confession! $$$\heartsuit$$$ $$$\heartsuit$$$ $$$\heartsuit$$$ $$$\heartsuit$$$

However, a complicating factor is the fact that Senpai's qualities/standards change continuously over time, and can be represented using the equation: $$$$$$ S_i(t) = F_i\cdot t + C_i $$$$$$

In this equation, $$$t$$$ represents the time passed so far, $$$F_i$$$ represents the change rate factor for the $$$i$$$th quality, and $$$C_i$$$ is the constant factor for that quality. We can assume that at the start, $$$t = 0$$$, and that $$$F_i$$$ and $$$C_i$$$ are constants.

Since you're pretty average, all of your quality scores $$$P$$$ start out at zero too ($$$P_i(0) = 0$$$ for all $$$i$$$). To catch up, you have a growth rate limit $$$g$$$, which denotes the limit at which you can improve your quality scores as described by the following formula: $$$$$$ \sum_{i=1}^{q} \left(\frac{d}{dt}P_i(t)\right)^2 \leq g^2 $$$$$$

This means that the combined magnitude of all rate of changes in qualities is less than or equal to $$$g$$$. The rate of change $$$\frac{d}{dt}P_i(t)$$$ doesn't even need to be positive or constant — the total magnitude just needs to be less than or equal to your growth rate limit $$$g$$$.

Each quality score as a function of time, $$$P_i(t)$$$, can then be any continuously differentiable function as long as they satisfy the above condition.

Combining all aforementioned equations to compare to Senpai's score: $$$$$$\begin{align*} P_i(0) &= 0 \, \text{for all $i$ from $1$ to $q$}\\ \sum_{i=1}^{q} \left(\frac{d}{dt}P_i(t)\right)^2 &\leq g^2 \\ S_i(t) &= F_i\cdot t + C_i \end{align*}$$$$$$

And to win Senpai's heart, it must be true that $$$$$$\sum_{i=1}^{q} S_i(t) \leq \sum_{i=1}^{q} P_i(t)\cdot W_i.$$$$$$

Help Kouhai find the smallest $$$t$$$ that can satisfy the above criteria assuming he improves his qualities $$$P_i(t)$$$ optimally.

Input

The first line of input contains a single integer $$$c$$$ denoting the number of test cases. The descriptions of the $$$c$$$ test cases follow.

The first line of each test case contains two space-separated positive integers $$$q$$$, and $$$g$$$; the number of qualities Senpai is looking at $$$q$$$, and Kouhai's growth limit with respect to time $$$g$$$.

A line containing $$$q$$$ space-separated integers follows, representing the weights $$$W_i$$$. The $$$i$$$th integer corresponds to $$$W_i$$$, the weight for the $$$i$$$th quality.

$$$q$$$ lines then follow, describing how Senpai's standards change over time. The $$$i$$$th line from which contains two space separated integers $$$F_i$$$ and $$$C_i$$$, the change rate factor and the constant factor for the $$$i$$$th quality ($$$S_i(t) = F_i\cdot t + C_i$$$).

Constraints

  • $$$1 \le c \le 10^3$$$.
  • $$$1 \leq q \leq 10^3$$$.
  • The sum of the $$$q$$$s in a single test file is $$$\leq 10^4$$$.
  • $$$1 \leq g \leq 5000$$$.
  • $$$-5000 \leq W_i \leq 5000$$$.
  • $$$-5000 \leq F_i, C_i \leq 5000$$$.
  • The answer exists and is at most $$$5000$$$
Output

For each test case, output a single line containing a single nonnegative real number $$$t_{\min}$$$, the earliest possible time $$$t \geq 0$$$ that Kouhai can win Senpai's heart.

Answers with an absolute or relative difference of at most $$$10^{-10}$$$ from the judge's answer will be accepted.

Example
Input
1
4 4
1 1 1 1
1 3
2 3
2 3
1 3
Output
6.00000000000
Note

The optimal way to achieve Senpai's standards is by distributing your growth rate like below:

  1. $$$P_1(t) = 2t$$$
  2. $$$P_2(t) = 2t$$$
  3. $$$P_3(t) = 2t$$$
  4. $$$P_4(t) = 2t$$$

This satisfies the constraints $$$$$$P_i(0) = 0$$$$$$ and $$$$$$\sum_{i=1}^{q} \left(\frac{d}{dt}P_i(t)\right)^2 \; \leq \; g^2.$$$$$$ With $$$P_i(t)$$$ like this, the earliest $$$t$$$ where $$$$$$\sum_{i=1}^{q} S_i(t) \leq \sum_{i=1}^{q} P_i(t)\cdot W_i$$$$$$ is $$$t = 6.0$$$. (Calculate the resulting $$$S_i(t)$$$ and $$$P_i(t)$$$ values to see.)

It can be shown that this is the minimum possible such $$$t$$$, among all possible choices of the $$$P_i$$$s.

D. Move to Remove Confidential Blunders
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The past year has not been very great for you and your team. So many embarassing mistakes have been made. And very public ones at that. With the advent of the Weirdly Wide Web, everyone now knows what you're doing. Clips of your team have been uploaded to the "Cloud" and anyone can watch it via UTube.

For instance, there was that one time when you tried to track an IP address using the GUI interface that you created with Visual Advanced.

Or that time when a hacker broke past your team's firewall, swiftly causing sparks to fly and creating actual fire in your department.

That time when you tried to launch a cybernuke.

Or asked the CCTV guy to rotate the picture 75 degrees around the vertical.

Of course, nothing beats the time when a computer virus took over during Freedom Day. As any beginning progammer can tell you, binary code is a series of ones and zeroes. The virus turned ones into zeroes and zeroes into ones, effectively reversing your code.

The list goes on. Downcast at this very long list of blunders, you wonder how you and your team will move forward. Fortunately, your VP, also known as Vision Possible, steps in and tells you of a plan to turn the situation around.

He calls it the "Move to Remove Confidential Blunders (MTRCB)". Explaining further, he says that the past mistakes were due to unsupervised access to usually confidential documents, movies, and other secrets. The key, therefore, is to implement a chain of command according to each person's capability, which is of course measured by age. Obviously, age determines everything about a person. It is a hierarchical world we live in, after all.

While you stand amazed at Vision Possible's ability to do the impossible, the MTRCB's rules are explained to you. Since generally, people are already responsible when they turn 18 years old, you now have these rankings:

  • "G" - no need for age-verification
  • "PG" - anyone below 13 years old should be accompanied by a responsible adult
  • "R-13" - none below 13 years old
  • "R-16" - none below 16 years old
  • "R-18" - none below 18 years old

Now, you must do your part in implementing these rules. You do your best as your team's success depends on this. Given a person's age, the corresponding ranking, and the title of what that person wants to access, say if you should grant access to that person.

Input

There is only one test case per file. The test case is formatted in two lines.

The first line contains an integer $$$a$$$ denoting the age of the person that you are checking access for, followed by a space, and then followed by a string denoting the corresponding ranking of what that person wants to access.

The next line contains the title of what the person wants to access.

Constraints

  • $$$0 \leq a\leq 10^9$$$
  • The title length, $$$\ell$$$, satisfies $$$1\leq \ell \leq 100$$$.
  • The ranking string is one of G, PG, R-13, R-16, R-18.
  • The title consists of characters whose ASCII values are between 32 and 126.
Output

Output a single line containing (without the quotes):

  • "OK" if you can give the person access,
  • "OK IF ACCOMPANIED" if you can give the person access if accompanied by a responsible adult, or
  • "ACCESS DENIED" otherwise.
Examples
Input
18 R-18
Frozen 3
Output
OK
Input
1 R-13
Star Wars: The Fall of Skywalker
Output
ACCESS DENIED
Input
13 PG
Agent Cody Banks
Output
OK
Input
1000 G
Die Hard: Finally Die
Output
OK
Input
15 R-16
Blaze Runner: 2049
Output
ACCESS DENIED
Input
9 PG
Hunger Games: Catching Firaga
Output
OK IF ACCOMPANIED
Input
10000 R-18
Karate Adult
Output
OK
Input
123456 G
Min Payne
Output
OK
Input
1 G
Mark of the Mini-Ninjas
Output
OK
Input
420 R-13
Team Fortress 5
Output
OK
Input
17 R-18
Heneral Looney
Output
ACCESS DENIED

E. A Floor of Many Doors
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ha HAHa haHA! You are the Mysterious Criminal Absconder, cunning trickster and nemesis of the Academy of Covert Missions.

Currently, you are on the top floor of their headquarters. HAHAHAh haha HAHH! (That's your "I'm hiding in my enemy's HQ" cackle.) In your hands is the top floor's floor plan in the form of a $$$r \times c$$$ grid. Each cell is a $$$1 \times 1$$$ square meter of space that is either a wall, a door, or an empty space.

You want to plant a bomb on this floor, and are planning to trigger it once someone enters the floor from downstairs. You've hacked the security system such that at most $$$k$$$ doors are allowed to be open at once. Once the agent arrives, all doors will be shut. From their current cell, they are only able to 1) walk to an adjacent cell that is either an empty space or an open door, or 2) open or close a door which is at a adjacent cell, both of which will take $$$1$$$ second each time they choose to do it. Of course, the agent will not be able to step on any space outside the floor plan's grid; they would fall out of the building.

Now, you've always loved playing games with this organization. To keep the game fair, you're going to have to plan this carefully in order to give them a chance to defuse this bomb. You must select 1) the cell where the agent will enter the floor and 2) the cell where the bomb will be, and determine if it is possible for them to reach the bomb. If it is, they must do so in the minimum time possible, else they will say goodbye to many precious files in their building.

Given the floor plan and the planned locations the two empty cells containing the agent's entrance and the bomb, would it be possible for the agent to defuse the bomb? If yes, what would be the minimum time for them to arrive at the cell containing the bomb?

Note: Two cells are considered adjacent if they share a common side.

Input

The first line of input contains $$$t$$$, the number of test cases.

The first line of each test case contains three space-separated integers $$$r$$$, $$$c$$$ and $$$k$$$. The $$$i$$$th of the next $$$r$$$ lines contains a string of length $$$c$$$ denoting the $$$i$$$th row. It consists of the following characters:

  • '.' denoting an empty cell;
  • '#' denoting a wall cell;
  • 'D' denoting a cell containing a door;
  • 'A' denoting an empty cell denoting the agent's entrance;
  • 'B' denoting an empty cell containing the bomb.

Constraints

  • $$$1 \le t \le 10^5$$$
  • $$$1 \le r, c, rc \le 5000$$$
  • $$$1 \le k \le 50$$$
  • The sum of $$$rc$$$ in a single file is at most $$$3\cdot 10^5$$$.
  • There is exactly one A in the grid.
  • There is exactly one B in the grid.
Output

For each test case, output a single line containing:

  • an integer denoting the minimum time for them to arrive at the cell containing the bomb; or
  • the string "HAHAHUHU" (without the quotes) if it is impossible for the agent to defuse the bomb.
Example
Input
2
3 12 3
....D...#.#B
A#.D.D..#.#.
.D..D...D.D.
7 11 8
......#....
......#..B.
##....#....
..#....####
...#...D...
...D...D...
...#...#.A.
Output
19
HAHAHUHU

F. One Great Grater
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You've spent the past couple of years as a Chugent, fulfilling various types of missions. You've infiltrated the Pentacontagon. You prevented the bombing that attempted to kill the not-so-rich King P'Taka. Despite doubts, you were also able to apprehend the master thief Pin Lu V. Amidst all these, you kept up with your daily regimen: 100 push-ups, 100 sit-ups, 100 squats, and a 10 km run. You kept at it every single day. You feel healthier than ever, but you think that your age is catching up to you as you notice your hair thinning for some reason.

With these thoughts in mind, you go to your mentor, the Great Spaitama. You tell him that it's time to be promoted from a Chugent to a full-fledged Jogent. He agrees, and presents you with a final test. He takes off and runs a few kilometers worth, but you are able to quickly follow him due to your daily training. You end up at the roof of what looks like a giant warehouse. You find and examine a secret door, and realize that it uses locks that are among the hardest to break into in the world. Thankfully, you are with no other than the Great Spaitama, who can open any lock with just ONE kick! It's not your first time seeing his technique, but you are still amazed at how he can kick the lock open without making any sound.

With the door open, you can now see the big rectangular room below you, and attached on one of the walls, you see something shiny.

"Is that a cheese grater?", you ask.

The Great Spaitama replies, "Not quite. You use it for fruits, and is worth a couple of thousands. A small, soft-spoken, client approached us to steal it."

He continues, "Note the floor tiles below. There are blue, red, and white tiles. Upon stepping on a blue tile, you end up turning and moving to your right. Stepping on a red tile sends you to your left. White tiles cause you to move forward."

He then hands you a pair of gloves. "Use these to stick onto the wall. Unfortunately, I can't drop you to the wall directly, and can only drop you on ONE specific tile. You can choose the direction (north, south, west, east) that you will be facing though. You just need to end up on a tile that will push you towards the wall. Let's call the border of a tile adjacent to the wall a "wall segment". You just need to end up at any of those wall segments; getting to the grater will then be easy with those gloves."

The following illustrates the "wall segments". There are five wall segments at the top and bottom walls each, and three wall segments at the left and right walls each.

"ONE last thing. Should you need it, I can help you change a white tile to either blue or red. Only ONE though, or it would be too easy for you. Understood?"

You tell The Great Spaitama that you are ready to begin. You still don't get his affinity with the number ONE. In any case, you try to impress him by not only getting to ONE wall segment, but telling him that you can actually get to other wall segments as well.

How many distinct wall segments can you possibly reach, if you can change at most one white tile to either blue or red?

Input

The first line of input contains a single integer $$$t$$$ denoting the number of test cases.

The first line of each test case contains two space-separated integers $$$h$$$ and $$$w$$$ denoting the height and width of the grid, respectively.

The next $$$h$$$ lines each contains a string of length $$$w$$$ denoting a row of the grid (from top to bottom). Each string consists of the following characters:

  • W denoting a white tile;
  • R denoting a red tile;
  • B denoting a blue tile;
  • S denoting the tile where you are dropped into. This tile is white.

Constraints

  • $$$1 \le t \le 10^4$$$
  • $$$1 \le h, w \le 10^5$$$
  • The sum of the $$$hw$$$ across all test cases is $$$\le 4\cdot 10^5$$$
  • There is exactly one S in the grid.
Output

For each test case, first output a single line containing a single integer $$$d$$$ denoting the number of distinct wall segments you can reach. Then, print $$$d$$$ lines describing these wall segments. Each of these lines contains a character $$$x$$$, a space, and then an integer $$$k$$$.

  • If the wall segment is at the top edge, then $$$x$$$ is the letter T, and $$$k$$$ denotes the column number from $$$1$$$ to $$$w$$$, from left to right.
  • If the wall segment is at the bottom edge, then $$$x$$$ is the letter B, and $$$k$$$ denotes the column number from $$$1$$$ to $$$w$$$, from left to right.
  • If the wall segment is at the left edge, then $$$x$$$ is the letter L, and $$$k$$$ denotes the row number from $$$1$$$ to $$$h$$$, from top to bottom.
  • If the wall segment is at the right edge, then $$$x$$$ is the letter R, and $$$k$$$ denotes the row number from $$$1$$$ to $$$h$$$, from top to bottom.

Output the wall segments in sorted order, first by increasing $$$x$$$ (alphabetically) and then by increasing $$$k$$$.

Example
Input
2
3 5
RBWWW
WWWWW
SWWBW
5 1
W
W
R
W
S
Output
10
B 1
B 2
B 3
B 4
L 1
L 2
L 3
R 1
R 2
T 3
6
B 1
L 3
L 4
L 5
R 4
R 5
Note

The following illustrates the sample input:

The gray wall segments cannot be reached. The remaining wall segments can be reached.

G. Generic Spy Movies
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

While fooling around at work today your boss, the head producer at Accelerated Creator of Movies (ACM), gives you a large list:

James Bold: Fingers

Missionary Possible: Callout

John Licks 3: Caramellum

Tom Clancy's Jack of Ryan

Fasting and Furious: Hobos with Shows

... (many more movies)

Your boss then tells you: "Slick, high-octane, spy thriller movie franchises are popular nowadays! Make $$$n$$$ movies like that!" and immediately leaves. With your jobs on the line, your hardworking team of writer-producers create the generic genre perfect spy movie scenario for you:

  • Since more movies = more money, you plan to create $$$n$$$ movies.
  • What's a spy film without a spy team? A cast of $$$g$$$ people seems to be the sweet spot: no more, no less.
  • To keep things interesting, one of the members needs to go into hiding/leave/die at the end of each movie. Preferably with a teary goodbye and matching melodramatic soundtrack.
  • To keep the cast the same number ($$$g$$$ members), someone must join the team at the start of every sequel. People love new faces. Maybe they're secretly someone who left a few movies before for a nice twist.
  • People will think you're redoing the plot of a previous movie if you got the exact same cast as before. The casting for each movie should not repeat across the entire franchise.

Seems good, right? You have just called all the agents your connections could afford, and not only they give you a list of $$$a$$$ actors to cast, but also that they have already booked the actors for the first episode! The only thing left is to decide the casting for the $$$n-1$$$ movie episodes left - but you remember that you can only change 1 slot in the cast after every movie ($$$1$$$ leaving the slot, $$$1$$$ arriving at that slot the next).

Given a list of actors $$$a$$$ and the initial lineup of $$$g$$$ cast members, list the cast changes needed to reach $$$n$$$ movies.

Input

The first line of input contains $$$t$$$, the number of testcases.

Each test case consists of three lines:

  1. The irst line contains three space-separated positive integers: $$$g$$$ (number of guests per episode), $$$n$$$ (the number of movies to produce), and $$$a$$$ (number of actors available for casting).
  2. Second line contains $$$a$$$ space-separated lowercase strings, the $$$i$$$th of which $$$a_i$$$ denotes the name of the $$$i$$$th castable actor.
  3. The third line contains $$$g$$$ space-separated lowercase strings, containing the names of the actors casted for the first episode.

Constraints

  • $$$1 \le t \le 50$$$
  • $$$1 \le g \le a$$$
  • $$$2 \le a \le 10^3$$$
  • $$$2 \le n \le 10^4$$$
  • Each $$$a_i$$$ has a length of at least $$$1$$$ and at most $$$4$$$.
  • You can always complete the casting for all $$$n$$$ episodes, i.e., a solution always exists.
Output

For each test case, output $$$n - 1$$$ lines, each containing two space-separated lowercase strings $$$a_\text{out}$$$ (actor being replaced) and $$$a_\text{in}$$$ (actor coming in).

Output a single blank line before the output of every test case except the first one.

There may be multiple valid answers; any one will be accepted.

Example
Input
2
2 4 4
ali bob carl dude
ali bob
2 4 5
ali bob carl dude earl
carl dude
Output
bob carl
carl dude
ali bob

dude earl
carl dude
dude ali
Note

Cast list for the first test case (bold text means a cast change occured):

  1. ali bob (first episode, no changes yet)
  2. ali carl (bob $$$\rightarrow$$$ carl)
  3. ali dude (carl $$$\rightarrow$$$ dude)
  4. bob dude (ali $$$\rightarrow$$$ bob)

H. Maggie and Dana's Mass Supper
time limit per test
6 seconds
memory limit per test
800 megabytes
input
standard input
output
standard output

Two best friends Maggie and Dana attend church mass at their hometown every Monday. They usually wake up at 10:00 am, attend mass at 11:23 am (the priest is really strict with regards to time), and finish at 3:00 pm. After that, most of their free time is spent reading books, finding stories, and keeping up to date with the news.

Today however, November 23 is a special day for both of them, as there's a supper happening this evening in their honor. Their other best friend Esmael has invited 58 guests in to his house to celebrate! Obviously, Maggie and Dana are very excited to attend the supper.

There's a slight problem though: the supper is located at the other end of region, so they have to walk across to get there! The region can be represented as an $$$\ell \times w$$$ rectangular grid, where the upper left corner is the church where Maggie and Dana will be coming from, and the bottom right corner being the supper location. Maggie and Dana can only move either directly downwards or rightwards (towards the destination).

Local bullies Andall and Zaldie hear about this, so they decide to make it hard for Maggie and Dana to get there. They decide to block specific parts of the region to limit Maggie and Dana's movement. For example, for $$$\ell = 7$$$ and $$$w = 5$$$:


...####
#...###
##...##
###...#
####...

Here, # represents a cell that is blocked, and . represents a cell that is not blocked.

They only leave a cascading path $$$\ell - w + 1$$$ wide for Maggie and Dana to get through! Maggie and Dana note that this is only possible due to their home province's unique geography, where its length is larger than its width ($$$\ell \gt w$$$). The cascading path shifts to the right by $$$1$$$ step for each row down in the region, where it ends at the bottom-right corner.

Now, Maggie and Dana want to know how many ways they can get to Esmael's supper, given that they are being blocked by Andall and Zaldie. Help them find that out!

Input

The input consists of a single line containing two space-separated integers $$$\ell$$$ and $$$w$$$, the length and width of the region Maggie and Dana live in.

Constraints

  • $$$1 \le w \le 5\cdot 10^5$$$
  • $$$1 \le \ell \le 5\cdot 10^6$$$
  • $$$w \lt \ell$$$
  • It is guaranteed that there is at least one path, i.e., the grid is not degenerate.
Output

Output a single line containing a single integer denoting the number of paths Maggie and Dana can take from the upper left corner (the church) to the bottom right corner (Esmael's supper), assuming Andall and Zaldie blocked the region in the way described above. Since the answer may be very large, only output it modulo $$$104857601$$$.

Example
Input
7 5
Output
16

I. Glory to Algotzka
time limit per test
2 seconds
memory limit per test
960 megabytes
input
standard input
output
standard output

Congratulations, comrade! You have won the labor ticket.

Report to the Auditing and Census Ministry (ACM).

Company Olympichia has been infiltrated by capitalists.

Algotzkan government needs to determine severity.

Your orders: evaluate compromisation for all inquiries.

Glory to Algotzka.

The structure of Company Olympichia is best described as a rooted tree. $$$n$$$ employee details have been given. Each detail includes which employee is the superior of another, and if they are suspected capitalist spies, or patriotic socialist comrades.

The Ministry has been given $$$q$$$ inquiries. Each inquiry contains an employee $$$i$$$ to be investigated, number of filthy capitalist spies $$$c$$$ and number of upstanding socialist comrades $$$s$$$.

You are required to give report on chain of command for each inquiry. A valid chain of command for employee $$$i$$$ is any connected subgraph that is rooted at $$$i$$$.

If there exists a valid chain of command with exactly $$$c$$$ cowardly capitalist spies and $$$s$$$ peerless socialist comrades, then company is compromised. Otherwise, it is not compromised.

Photos taken from https://munkahelyiterror.blog.hu/2012/07/17/lekurvazott_es_fizikailag_bantalmazott_az_elelmezes_vezeto and https://ycl.org.uk/ licensed under https://creativecommons.org/licenses/by-nc-nd/3.0/

Input

There is one test case for each input file.

Input starts with one line containing two space-separated integers $$$n$$$ and $$$q$$$, the number of employees and inquiries respectively. The employees are numbered from $$$1$$$ to $$$n$$$.

The second line contains a list of $$$n$$$ space-separated integers $$$E_1, E_2, \ldots, E_n$$$: the Olympichia employee details given to you by the government of Algotzka. The $$$j$$$th number $$$E_j$$$ in the list corresponds to the employee number which is the direct superior of the one in the list. The first number in this list $$$E_1$$$ (counting starts at $$$1$$$) is always the root node for the entire company; we will denote this by having $$$E_1 = 0$$$.

The third line contains a string of length $$$n$$$, $$$A = A_1A_2\ldots A_n$$$ denoting the affiliations of the Olympichia employees described above. The $$$j$$$th character, $$$A_j$$$, can only be one from the following:

  1. C: $$$j$$$th employee is a dastardly capitalist.
  2. S: $$$j$$$th employee is a unwavering socialist comrade.

Then $$$q$$$ lines follow. Each line contains three space-separated integers $$$i$$$, $$$c$$$, and $$$s$$$. This represents each inquiry made by the Algotzkan government.

Constraints

  • $$$1 \le n \le 10000$$$
  • $$$1 \le q \le 200000$$$
  • $$$1 \le i \le n$$$
  • $$$0 \le c, s \le 10000$$$
  • $$$c + s \gt 0$$$
  • The length of $$$A$$$ is $$$n$$$.
  • Each $$$A_j$$$ is either C or S.
  • $$$E_1 = 0$$$
  • $$$1 \le E_j \lt j$$$ for $$$1 \lt j \le n$$$
Output

Output one line for each inquiry, containing the result of the investigation (without the quotes):

  • "COMPROMISED" If there exists a connected subgraph in the subtree rooted at employee $$$i$$$ with exactly $$$c$$$ capitalists and exactly $$$s$$$ socialists.
  • "NOT COMPROMISED" If no such connected subgraph exists.
Example
Input
5 3
0 1 2 3 4
CSCSC
1 3 2
1 2 2
2 2 1
Output
COMPROMISED
COMPROMISED
NOT COMPROMISED

J. A Cold Macchiato
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Spies are usually seen with a cocktail or some other booze in hand. Even if you don't actually like cocktails yourself, at the very least you'd have to blend in to find your target in their favorite bar. After all, shady business transactions are usually done in such dark, relaxing, and hidden places. Sneaking something into your target person's drink is something that you, the best spy in the world, have done many times, and you have just been assigned another target to add to your super long long list of successful missions.

Except that this time, your target is an Asian king named Mr. Bin. And Mr. Bin doesn't like cocktails. Instead, after gathering intel, you found out that Mr. Bin has negligible ankles, likes coffee, and has a very adorable cat named Soseol. Your colleagues thought that you were slacking off when they saw you scrolling through Tweetur, but you were actually browsing Mr. Bin's daily posts of himself, his coffee, and his cat at the subtle coffee shop Covert Feline caFe. You were totally doing research and not spending hours looking at Soseol.

You don't know what Mr. Bin did to become a target, but you were told to disguise yourself as a barista at the Covert Feline caFe and put some sugar in Mr. Bin's favorite coffee drink. You don't know why it's sugar specifically since you usually used some other harmful substance in your past missions. Maybe it's to ruin his diet (pure evil). Or maybe he's actually allergic to sugar, who knows?

Sneaking in the sugar is the easy part. The trickier part is preparing the coffee, since you have never prepared coffee before. You don't drink coffee as you never needed the extra caffeine, being the excellent spy that you are. Upon observing the cafe, you noticed that there are three dispensers (cold, neutral, and hot), each giving water at a specified temperature. To prepare Mr. Bin's drink, the water has to be within a certain temperature range, and you achieve this by getting and mixing water from the three dispensers. When you mix water this way, the resulting drink gets the average temperature of the three dispensers, weighted by their respective volumes.

Furthermore, cats usually run around the cafe, causing the dispensers to malfunction. Each dispenser has a chance of malfunctioning, and when it does, it could end up dispensing water with the temperature of the other dispensers instead. At most one dispenser malfunctions.

As you need to be in perfect disguse as a barista, you should be able to know the volume of water that you will get from each dispenser. You must select it in a way that maximizes the probability that the drink ends up with a temperature that is within the acceptable range.

You may get any nonnegative real amount of water (in milliliters) from each dispenser, as long as the total volume is exactly $$$1000$$$ milliliters.

Input

The first line of input contains an integer $$$b$$$, the number of Covert Feline caFe branches that Mr. Bin visits, followed by the descriptions for each branch.

The first line of each branch contains three integers $$$t_1, t_2, t_3$$$ denoting the respective temperatures for the three dispensers (cold, neutral and hot), separated by single spaces.

The second line for the branch contains three fractions denoting the respective probabilities of the three dispensers to malfunction, separated by a space. The $$$i$$$th fraction, $$$m_{i,\text{(n)}}/m_{i,\text{(d)}}$$$, denotes the probability that the $$$i$$$th dispenser malfunctions.

Then three lines follow. Each of these lines contains three probabilities separated by single spaces, expressed as a fraction of two integers. The $$$j$$$th fraction in the $$$i$$$th line, $$$d_{i,j,\text{(n)}}/d_{i,j,\text{(d)}}$$$. represents the probability that the $$$i$$$th dispenser releases water at the temperature of the $$$j$$$th dispenser if the $$$i$$$th dispenser malfunctions.

The next and final line for the branch contains two space-separated integers $$$l$$$ and $$$u$$$, where $$$l$$$ and $$$u$$$ are the lower and upper bounds for the acceptable range of temperatures. The bounds are inclusive.

Note: The temperatures and volumes are given in units used internally by spies. As these are used in the secret formulas for certain secret substances, the actual conversions to common SI metric units are not disclosed publicly.

Each probability is written as x/y where x and y are integers.

Constraints

  • $$$1 \le b \le 1200$$$

  • $$$-273 \le t_1, t_2, t_3, l, u \le 10^6$$$
  • $$$t_1 \lt t_2 \lt t_3$$$
  • $$$l \le u$$$

  • $$$0 \le m_{i,\text{(n)}}, d_{i,j,\text{(n)}} \le 10^3$$$ (these are integers)
  • $$$1 \le m_{i,\text{(d)}}, d_{i,j,\text{(d)}} \le 10^3$$$ (these are integers)

  • The sum of all $$$\frac{m_{i,\text{(n)}}}{m_{i,\text{(d)}}}$$$ is $$$1$$$.
  • For each $$$i$$$, the sum of all $$$\frac{d_{i,j,\text{(n)}}}{d_{i,j,\text{(d)}}}$$$ is $$$1$$$.
Output

For each branch, output a line containing a single fraction denoting the maximum probability that the drink is within the allowable temperature range, if the amounts obtained from the dispensers are chosen optimally. Print it as a fraction "x/y" (without the quotes) in lowest terms and with positive denominator. If the probability is $$$0$$$, output "0/1" (without the quotes). If the probability is $$$1$$$, output "1/1" (without the quotes).

Example
Input
1
37 38 39
1/5 3/5 1/5
1/3 1/3 1/3
1/3 1/3 1/3
1/3 1/3 1/3
36 38
Output
14/15

K. I Brook the Code!
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

"Beats like digits. Every beat is one. Every rest is a zero. Binary code. That's why all those assassins tried to save my life. It was hidden on me, hidden inside my head. A few simple lines of computer code that can break into any system."

Armed with this very dangerous weapon, you now need to send this information to your trusty friend John. Unfortunately you and John have no access to things like HTTPS or encrypted e-mail. Instead, you have agreed beforehand to send the needed numbers in the following very elaborate manner: You will send a total of $$$n$$$ people to John's apartment. Then John will record every person's weight in micrograms and height in nanoinches. After $$$n$$$ people visit in total, John can now extract the secret computer code as precisely the (integer) sequence of weights (in micrograms) if the $$$n$$$ people are sorted by height.

You already have these "encrypted" numbers. Can you verify that you can get back the secret computer code?

It is guaranteed that no two people have the same height (in nanoinches).

Input

The first line of input contains a single integer $$$n$$$.

The second line of input contains $$$n$$$ space-separated integers $$$w_1, w_2, \ldots, w_n$$$ denoting the weights of the $$$n$$$ people in micrograms.

The third line of input contains $$$n$$$ space-separated integers $$$h_1, h_2, \ldots, h_n$$$ denoting the heights of the $$$n$$$ people in nanoinches.

Constraints

  • $$$1 \le n \le 10^5$$$
  • $$$1 \le w_i, h_i \le 10^{11}$$$
  • The $$$h_i$$$ values are distinct.

(In other words, some of these people are microscopic.)

Output

Output a single line containing $$$n$$$ space-separated integers denoting the secret computer code.

Example
Input
3
2 1 4
1 4 3
Output
2 4 1

L. Break the Pattern!
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Tasked with finding new recruits for the Division of Cryptographic Secrets, you put up a place where you can observe people's talents in finding clues, solving puzzles, and uncovering mysteries: an Escape the Room game!

You've thought of something that can be used to unlock one of the doors in the Room. To get feedback, you've approached your friends Andy, Natalie, and Dylan.

You ask them, "Complete the pattern: 1, 2, 3, 5, X. What is X?"

Andy quickly answers, "8! Isn't it just the Fibonacci sequence?"

Almost immediately, Natalie says, "Could also just be the roots of $$$x^5 - 19x^4 + 129x^3 -389x^2 + 518x - 240$$$."

Dylan then adds, "Isn't it a bit ambiguous? Technically you could have any piecewise function. How about adding some constraints?"

You take their feedback into account. After contemplating for a bit, you propose a variant. "Alright, how about this. Given the sequence, output $$$n$$$ distinct nonzero polynomials that 'fit' the sequence, with maximum degree $$$k$$$."

This variant seems fair enough to them. "Time to test the puzzle then," they say. Andy, Natalie, and Dylan take turns in giving you random sequences, while you need to reply with the different polynomials that could fit those sequences. Here, "fitting" means that the polynomial will evaluate to zero for all of the integers in the given sequence.

Input

The first line of input starts with an integer $$$t$$$, the number of sequences.

$$$t$$$ sequences follow, described in two lines each.

The first line for each sequence consists of three integers $$$n$$$, $$$k$$$, and $$$\ell$$$, each separated by a space. $$$n$$$ and $$$k$$$ are as described previously, while $$$\ell$$$ denotes the length of the sequence.

The second line for each sequence contains the $$$\ell$$$ integers $$$s_1, s_2, \ldots, s_\ell$$$ that make up the sequence, separated by single spaces.

Constraints

  • $$$1 \le t \le 2500$$$
  • $$$1 \le n, k, \ell \le 50$$$
  • $$$-400000 \le s_i \le 400000$$$
Output

For each of the $$$t$$$ sequences, output the following:

If less than $$$n$$$ such polynomials exist, print how many there are on its own line, followed by those polynomials. If there are at least $$$n$$$, print $$$n$$$ on its own line, followed by any $$$n$$$ polynomials.

Output each polynomial on each own line. First output its degree $$$d$$$, followed by exactly $$$d+1$$$ space-separated integer coefficients in decreasing order of exponents. The leading coefficient must not be zero.

The absolute value of the coefficients must also be less than or equal to $$$10^9$$$.

Important: For this problem, we treat the integers as congruent modulo $$$999983$$$. In other words, two integers $$$x$$$ and $$$y$$$ are considered equal if $$$999983$$$ divides $$$x - y$$$. (This implies that two polynomials $$$p$$$ and $$$q$$$ are considered equal if every coefficient of $$$p - q$$$ is divisible by $$$999983$$$. For example, $$$x - 1$$$ is considered the same as $$$999984x + 999982$$$, etc.)

There may be multiple valid answers. Any valid answer will be accepted.

Example
Input
3
1 5 4
1 2 3 5
1 3 4
1 2 3 5
1 4 3
3 7 42
Output
1
5 1 -19 129 -389 518 -240
0
1
4 1 -52 441 -882 0
Note

Note that 5 1 999964 129 -389 518 999743 is also a valid output for the first test case and is equivalent to the sample output above. (For example, evaluating it at $$$1$$$ will give $$$1999966$$$ which is equivalent to $$$0$$$ since $$$1999966 - 0$$$ is divisible by $$$999983$$$, so $$$1$$$ is a root.)

M. Thin Ice
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

So you, as well as every member of the Penguin Secret Agency (PSA), have successfully sunk the evil genius's secret iceberg base by dancing on it until it flipped. He's pretty mad about that and went back to his igloo as a result. However, intelligence reports say that he has a special ice farm to create a second Iceberg Base.

You move to his ice farm and realize that you don't have anything to melt the ice with. You did however, bring your Puffle. After giving it a berry, it bursts into flames, ready to melt the ice for you, turning it into water. There is a problem though: if the Puffle is forced to go into the water, it cannot melt any more ice blocks. Also, you must melt all the ice to prevent the second Iceberg Base. Lastly, you need to give your Puffle instructions on how to move. They aren't known for their puzzle solving skills, but their memory is excellent. Don't forget to pick up your Puffle after it's done. Good luck!

The area to solve is an $$$r\times c$$$ grid. We denote by $$$(i, j)$$$ the cell at the $$$i$$$th row (from the top) and the $$$j$$$th column (from the left). In particular, $$$(1, 1)$$$ is the top-left corner of the area.

Your starting position is cell $$$(i, j)$$$, and your ending position can be anywhere.

Determine if a path that goes through each cell exactly once is possible. You are considered to have already passed the starting cell at the beginning. If it is possible, give a sequence that will do so.

Output your instructions as a sequence of directions: up, down, left, or right.

Should it be impossible, say so as well.

Input

The first line of input contains $$$t$$$, the number of test cases.

Each test case consists of a single line containing four space-separated integers $$$r, c, i, j$$$.

Constraints

  • $$$1 \le t \le 10^5$$$
  • $$$1 \le r, c \le 100$$$
  • $$$1 \le i \le r$$$
  • $$$1 \le j \le c$$$
  • $$$rc \gt 1$$$
  • It is guaranteed that the output file is at most 10 Megabytes ($$$10^7$$$ bytes).
Output

For each test case, output a single line containing a single string which is either:

  • a string consisting of the following characters:

    • U - Moves your position up by 1
    • L - Moves your position left by 1
    • D - Moves your position down by 1
    • R - Moves your position right by 1

  • the string "IMPOSSIBLE" (without the quotes) if the task is impossible.
For example, if an answer requires you to move right, then down, then left, then the output will be RDL. There may be multiple answers; any one will be accepted.
Example
Input
2
2 3 1 1
3 3 1 2
Output
DRRUL
IMPOSSIBLE