UTPC Contest 10-23-20 Div. 2
A. Mr. Skeleton
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Skeleton is a groovy guy. He has $$$N$$$ bones. Wait, wait a minute, he thought he had $$$N$$$ bones. 1, 2, 3, 4...aw crap, not again. He swears he had $$$N$$$, they were just here!

Well, it's hard being a skeleton, and sometimes you just have to pick yourself up off the ground, even if that means literally. As in literally going back and picking up pieces of your body where they fell off and you forgot them.

Help Mr. Skeleton figure out which bones he's missing this time. Given that Mr. Skeleton normally has bones $$$1$$$ through $$$N$$$ and now he only has some subset of those bones still attached, $$$H$$$ of them to be precise, compute the list of lost bones that Mr. Skeleton has left to find!

Input

The first line contains two integers: $$$N$$$ ($$$1 \leq N \leq 10^5$$$), the total number of bones that Mr. Skeleton normally has when he has all of his bones, and $$$H$$$ ($$$1\leq H \leq N$$$), the number of bones he currently has on him. The next $$$H$$$ lines each contain the name $$$b_i$$$ ($$$1 \leq b_i \leq N$$$) of one of Mr. Skeleton's unique bones that he has verified is currently in his possession (i.e. not missing).

Output

Print out the numeric name of each bone that Mr. Skeleton is still missing. The bone names should be printed out on separate lines, in order from least to greatest number.

Example
Input
9 4
2
1
7
5
Output
3
4
6
8
9

B. Heading Home
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Abhinav is far away from his home on Halloween night! He's incredible scared of being attacked by ghosts, so he wants to run home as quick as he can to maximize his chance of making it through the night safely.

We can model Abhinav's position and his home's position as points on a number line as $$$a$$$ and $$$h$$$, respectively. In a single second, Abhinav can move anywhere between $$$1$$$ and $$$d$$$ units. Given $$$a$$$, $$$h$$$, and $$$d$$$, can you figure out how fast Abhinav can make it back home?

Input

The first line will consist of a single integer $$$T$$$ ($$$1 \leq T \leq 1000$$$) consisting of the number of test cases you will need to process. The next $$$T$$$ lines each consist of a single test case with $$$3$$$ space separated integers $$$a$$$, $$$h$$$, $$$d$$$ ($$$1 \leq a, h, d \leq 10^5$$$), which represent Abhinav's position, his home's position, and his max speed.

Output

For each test case, output a single integer giving the minimum amount of time (in seconds) it will take Abhinav to reach his home.

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

C. Optimal Trick or Treating
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Little Timmy is going trick or treating this year, but has decided that he will only look for his favorite kind of candy: Chuckles bars. Unfortunately, Alice has bought up all of the Chuckles bars in the neighborhood and using them to trade for other candies, so Timmy must find the candies that Alice is looking for and trade them in for Chuckles bars. Alice has posted $$$n$$$ types of trades that she is willing to make, where a trade consists of a type of candy and how many Chuckles bars Alice is willing to give for one piece of that type of candy.

Little Timmy has done extensive research and discovered what candies and amounts each of the $$$h$$$ houses in his neighborhood is going to be giving out. When Little Timmy goes to a particular house, he can take all of the candy that the house is giving out. However, he only has time to visit $$$k$$$ different houses before the night ends. Given the candies that each house gives out and the deals Alice is willing to make, what is the maximum amount of Chuckles bars that Little Timmy can end up getting?

Input

The first line of the input will consist of a single integer $$$n$$$ ($$$1 \leq n \leq 200$$$), which gives the number of deals that Alice is willing to make. The next $$$n$$$ lines of the input will consist of a string $$$s_i$$$ made of only alphanumeric characters ($$$1 \leq |s_i| \leq 15$$$) and an integer $$$v_i$$$ ($$$1 \leq v_i \leq 100$$$), which indicates that Alice is willing to give $$$v_i$$$ Chuckles bars for a single candy with the name $$$s_i$$$. The next line of the input will consist of two integers $$$h$$$ and $$$k$$$ ($$$1 \leq k \leq h \leq 200$$$), which gives the number of houses in Timmy's neighborhood and the number of houses that he can visit. The next lines of the input consist of $$$h$$$ house-descriptions, which consist of a single integer $$$c_i$$$ ($$$1 \leq c_i \leq n$$$) giving the number of types of candies that house $$$i$$$ is giving out, followed by $$$c_i$$$ lines that each consist of one of the $$$n$$$ types of candies that Alice is willing to send and an integer $$$m_j$$$ ($$$1 \leq m_j \leq 100$$$) that gives the number of candies of that type that house $$$i$$$ is giving out.

Output

Output a single integer and new line that gives the maximum number of Chuckles bars that Little Timmy can end up collecting.

Example
Input
3
LactoseyWay 2
Twicks 3
DigDog 5
2 1
2
LactoseyWay 3
Twicks 1
1
DigDog 2
Output
10

D. Ghost-or-Treat
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

King Boo has $$$N$$$ ghosts standing in a line. This year, they decide that they want to go ghosting and treating. While trick-or-treating is relatively simple for humans, for ghosts, instead they need to scare people and steal their candy when they're terrified. But, being ghosts, they're kind of lazy, and so Boo has decided a system where only one ghost will go out and do this task this year so everyone can have some candy.

Every single ghost has been a ghost for a certain number of whole number years. Boo has decided to repeatedly pick out two ghosts with different "ages" that are adjacent to each other in the line, and if one of them has been a ghost longer than the other, the younger ghost will step out of line and is no long in the running to be a ghost-or-treater. However, matches are tiring to the participants involved, so the ghost that stays in line will effectively age a year. This process repeats until all Boo can no longer select two ghosts, and Boo will declare the remaining ghost(s) the "winner(s)" to go ghost-or-treating.

Given the ages of each of the ghosts in order, is there a way that Boo can set up the matches such that only one ghost will have to go ghost-or-treating (in other words, only one ghost will be remaining in line)?

Input

The first line will contain $$$N$$$ $$$(1 \le N \le 10^4)$$$, the number of ghosts.

The next $$$N$$$ lines will each contain the age $$$X$$$ $$$(1 \le X \le 10^9)$$$ of a ghost in years.

Output

Output YES if it is possible to send out exactly one ghost, and NO if not.

Examples
Input
5
5
3
4
4
5
Output
YES
Input
3
1
1
1
Output
NO
Input
5
4
4
3
4
4
Output
YES
Note

In the first sample case, the matchups can be the following:

1st ghost v.s. 2nd ghost, 1st ghost stays in line and is now 6 years old

1st ghost v.s. 3rd ghost, 1st ghost stays in line and is now 7 years old

4th ghost v.s. 5th ghost, 5th ghost stays in line and is now 6 years old

1st ghost v.s. 5th ghost, 1st ghost stays in line and no one else is left

Note that the 1st ghost and 3rd ghost are adjacent after the 2nd ghost steps out of line when the first matchup completes.

E. Spooky Numbers
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Francine loves pranks. Her friend, Buster, is not a Halloween fan and during the course of October, he has an unnatural fear of any non-negative number which is divisible by $$$2$$$, $$$3$$$, and $$$5$$$. At the sight or mention of any of these 'spooky' numbers, Buster jumps a little bit. Francine, always on the lookout for good prank opportunities, has noticed a pattern: the larger the 'spooky' number, the higher Buster seems to jump. Curious to see how high she can get him to jump, she wants comes up with a huge 'spooky' number and print the digits individually, and put the number across the school football field for Buster to see before practice. She finally gets to a 'spooky' number that she was happy with but then her friend Arthur got a hold of her laptop before she sent the order to be printed and added some random digits. Francine, unfortunately, did not realize Arthur's prank until after she sent the order to be printed and now she realizes that she is going to get more digits than she wanted.

In order to salvage the prank and not waste the digits she is getting, she asks you for help. She wants the largest 'spooky' number that can be made from the $$$n$$$ digits that she is having printed such that there are no leading zeros (leading zeros don't bother Buster so Francine doesn't want to go through all the effort of putting them up for no reason). Your job is to output the largest 'spooky' number that she can make with the $$$n$$$ digits she has (or output $$$-1$$$ if there was a catastrophic error in Francine's calculations such that she cannot make a 'spooky' number with her digits).

Input

The first line of input will contain a single integer, $$$n$$$ (where $$$1 \leq n \leq 10^{5}$$$), representing the number of digits Francine has.

The second line of input will have $$$n$$$ space-separated integers, where the $$$i$$$th number will be $$$d_i$$$ (where $$$0 \leq d_i \leq 9$$$) representing the value of a single digit that Francine has.

Output

The largest 'spooky' number that Francine can make with her digits (without any leading zeros) or $$$-1$$$ if it is not possible to make a 'spooky' number.

Examples
Input
1
0
Output
0
Input
6
2 3 1 3 1 0
Output
33210
Note

In the first example, the only digit is $$$0$$$ so there is only one 'spooky' number which can be made, namely $$$0$$$. In the second example, the largest 'spooky' number that can be made is $$$33210$$$, no number which includes all $$$6$$$ of the digits can be divisible by $$$3$$$ so this is the best we can do.

F. Xorro the Xorman
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Erik forgot to make a costume for this year's Halloween festivities, which means he has to reuse his old Zorro outfit from last year. However, he doesn't want to be ridiculed by his friends for his laziness, so Erik rebrands himself as Xorro the Xorman. Instead of slashing a 'Z' on his enemies defeated in sword combat, Xorro will carve an 'X' onto whomever cannot answer his question involving the XOR bitwise operator. You meet the infamous Xorman while trick or treating, and are given two integers $$$A$$$ and $$$B$$$. Xorro wants you to tell him the maximum possible XOR of $$$A$$$ and $$$b$$$ for some integer $$$0 \leq b \leq B$$$. If you fail to answer correctly, Erik will strike in retaliation. Can you avoid the wrath of Xorro?

Input

The first and only line of input contains two integers $$$A$$$ and $$$B$$$ such that $$$0 \leq A, B \leq 10^{18}$$$.

Output

Output a single integer representing the answer to Xorro's query, the maximum possible value of $$$A \oplus b$$$.

Examples
Input
5 4
Output
7
Input
7 32
Output
39

G. Hyper Chocolate Cubes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Felix is going trick or treating this year! Last year, he was not able to get enough chocolate, and the year before, he got too much, and he had to throw some away. This year, after carefully planning out exactly how much chocolate he is going eat for the next month, he decides that he wants exactly $$$x$$$ cubes of chocolate.

However, once Halloween arrived, Felix forgot all about his precise amount of chocolate that he wanted and he ran down the street and grabbed a piece of chocolate from every house along the way. Felix lives on a very weird street with $$$100$$$ houses, and turns out, while the first four houses simply give out respectively 1 chocolate cube, $$$w$$$ chocolate cubes in a line, $$$w^2$$$ chocolate cubes in a square, and $$$w^3$$$ chocolate cubes in a $$$w \times w \times w$$$ cube, from the 5th house onwards, things actually continue! By the time Felix hits the $$$100^{th}$$$ house, he is getting an $$$100$$$-dimensional hypercube with sidelength $$$w$$$, and hence getting $$$w^{100}$$$ chocolate cubes.

Now, this does not really matter to Felix, since he just wants the right amount of chocolate. Turns out, his mother knew about his endeavors and decided to buy him some chocolate that she claims is the exact amount of chocolate that Felix wants. Felix however does not believe his mother and with his $$$n$$$ hypercubes of chocolate and his trusty balance scale, he decides to see if he can determine if his mother really did get him the right amount of chocolate. Help Felix find out if he can determine the exact amount of chocolate cubes in the package his mother gave him to help out his task!

Given that Felix does not want to break his cubes of chocolate, he will only use it in the shape that it was given to him, determine if there is a way to arrange some subset of his cubes of weight $$$1, w, w^2, \ldots, w^{100}$$$ can be put on either side of the balance scale, with his mother's chocolate on one side such that the scale balances.

Input

The first line of the input will contain integers $$$n$$$ ($$$1 \le n \le 20$$$) and $$$w$$$ ($$$2 \le w \le 10$$$), the number of packages Felix wants to test and the side length of the hypercubes, respectively.

The next $$$n$$$ lines will each contain a single integer $$$x_i$$$ ($$$1 \leq x_i \leq 10^9$$$), the hidden weight of the $$$i$$$-th package.

Output

Output $$$n$$$ lines, each with YES if it is possible to balance the scale, and NO if it is not possible to balance the scale.

Example
Input
4 5
25
26
29
32
Output
YES
YES
YES
NO
Note

For the first weight of $$$25$$$ is on one side of the balance, you can simply place the square of cubes (of weight $$$5^2$$$) on the other side of the balance. If the weight is $$$26$$$ is on one side, you can place the square of cubes (weight $$$5^2$$$) and a single cube (weight $$$1$$$) on the other side of the balance. If the weight is $$$29$$$ on one side, then you can place a single cube (weight $$$1$$$) on the same side as that weight and then place the square of cubes (weight $$$5^2$$$) and the line of cubes (weight $$$5$$$) on the other side and it will be balanced.

H. Slime-inator
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Dr. Heinz Doofenshmirtz has been waiting to get his revenge on the Tri-state Area and his 'perfect' brother, Mayor Roger Doofenshmirtz. Mayor Doofenshmirtz and the prodigal twins, Phineas and Ferb, have organized a city-wide trick-or-treat scavenger hunt for the city's children. Dr. Doofenshirmtz figures that this is his chance to sabotage his brother's popularity and creates the 'Slime-inator', a device that fills the streets with a gooey slime that makes it impossible to walk or drive around, never mind trick-or-treat. Major Monogram, as always, has got wind of Doofenshmirtz's evil plan and calls for his trusty agent, Perry the Platypus, to save the kids trick-or-treat experience.

Now, the city of Danville was meticulously planned when it was built so it can be broken down into an $$$n \times n$$$ square grid with each of the squares having equal size. Dr. Doofenshmirtz releases his slime from Doofenshmirtz Tower at position $$$(x,y)$$$ in the grid at time $$$t=0$$$ seconds. Each second, the slime moves into each of the four adjacent squares of anywhere it is at currently (so if it is currently at $$$(x,y)$$$ it will go to $$$(x-1,y)$$$, $$$(x+1,y)$$$, $$$(x,y-1)$$$, and $$$(x,y+1)$$$ in the next second - provided all those locations are in the range of the city, Doofenshmirtz is environmentally conscious so he has engineered the slime to not cross the borders of the city grid). The trick-or-treat event will be completely ruined and unsalvageable if at least $$$k$$$ of the city's grid squares are covered by slime. Help Perry determine the number of seconds it will take for at least $$$k$$$ of the squares in the grid of the city to be covered in slime so that he can get to Doofenshmirtz in time and save the trick-or-treat event!

Input

The first line of input will contain four space-separated integers, $$$n$$$, $$$x$$$, $$$y$$$, and $$$k$$$ representing the side length of the city grid, the row in the grid Doofenshmirtz tower is at, the column in the grid Doofenshmirtz tower is at, and the number of grid squares that must be covered before the event is unsalvageable, respectively. ($$$1 \leq n \leq 10^{9}$$$, $$$1 \leq x,y \leq n$$$, and $$$1 \leq k \leq n^{2}$$$)

Note, $$$k$$$ can be up to $$$10^{18}$$$ (if $$$n = 10^{9}$$$) so use your language's appropriate data type for these values and corresponding computations (long in Java and long long in C++ for example).

Output

Output a single number, representing the minimum number of seconds until at least $$$k$$$ squares in the grid are covered in slime.

Examples
Input
4 3 2 1
Output
0
Input
10 7 3 7
Output
2
Note

In the first example, the slime starts off in one grid square at time $$$0$$$ (namely position $$$(3,2)$$$) which is $$$\geq k$$$ meaning that Perry was too late and the event is already unsalvageable. In the second case, after $$$1$$$ second, the slime will cover $$$5$$$ grid squares and then after $$$2$$$ seconds, it will cover $$$13$$$ squares which is more than $$$k$$$ so Perry must stop Doofenshmirtz before $$$2$$$ seconds passes.