UTPC x WiCS Contest 04-05-23 (UT Internal)
A. Ordering Cupcakes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice is hosting a cupcake party to celebrate cupcake day but isn't sure what to order. To make things easier, Alice gives each of her $$$N$$$ guests a list $$$M$$$ of cupcake flavors and asks them to pick their favorite one. Each flavor can be represented by integer $$$f_i \ (1 \leq f_i \leq M)$$$

As she started ordering, Alice realized that her local bakery only sells cupcakes in dozens. She needs you to help her determine how many dozen of each cupcake to buy so that she minimizes the number of cupcakes she buys while ensuring that everyone can eat at least one cupcake of their favorite flavor.

Input

The first line of input will contain two space-separated integers, $$$N\ (1 \leq N \leq 10000)$$$, the number of guests she plans to invite, and $$$M\ (1 \leq M \leq 100)$$$, the number of flavors the bakery sells.

The second line of input contains $$$N$$$ space-separated integers $$$f_i\ (1 \leq f_i \leq M)$$$, where $$$f_i$$$ represents the $$$i$$$th guest's favorite flavor.

Output

Output $$$M$$$ lines of output, where the $$$i$$$th line consists of a single integer representing how many dozen of flavor $$$i$$$ Alice should buy for her party.

Examples
Input
3 2
1 2 1
Output
1
1
Input
14 2
1 1 1 1 1 1 1 1 1 1 1 1 1 2
Output
2
1
Note

In the second test case, 13 guests want flavor 1. We have to order 2 dozen of flavor 1 because if we only ordered one dozen (12), we would be one cupcake short.

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

Meg is buying cupcakes for her friend's birthday at Polkadots Cupcake Factory. *This problem is not sponsored by Polkadots Cupcake Factory and does not express the views of Polkadots Cupcake Factory.

All of the cupcakes have some number of polkadots on them. Meg would like to buy a cupcake with at least $$$n$$$ polkadots on it. However, it's well-known that cupcakes with a prime number of polkadots are bad luck. Please help Meg determine how many polkadots her cupcake should have, such that

  • The cupcake has at least $$$n$$$ polkadots,
  • The cupcake has as few polkadots as possible, and
  • The cupcake does not have a prime number of polkadots.
Input

The first and only line contains a single integer $$$n$$$ denoting the minimum number of polkadots Meg wants. $$$(2 \le n \le 1000)$$$

Output

Output a single integer, the minimum number of polkadots Meg's cupcake should have that is not prime and is greater than or equal to $$$n$$$.

Examples
Input
2
Output
4
Input
5
Output
6
Input
1000
Output
1000

C. Frosting Circles
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Polycarp is baking a cupcake and first bakes the bread, which can be represented as a solid circle centered at $$$(0, 0)$$$ with radius $$$R\ (1\leq R\leq 50).$$$ Polycarp also puts down $$$N$$$ $$$(1\leq N\leq 50)$$$ solid circles of frosting, with the $$$i$$$th one having radius $$$r_i\ (1\leq r_i\leq 50)$$$ and centered at $$$(x_i, y_i)$$$ $$$(-50\leq x_i, y_i\leq 50)$$$.

Polycarp wants to know how many integer points of the cupcake bread are covered by least one of the circles of frosting. Can you help Polycarp?

Input

The first line contains $$$N, R$$$ in that order.

The next $$$N$$$ lines will contain $$$r_i, x_i, y_i$$$ on the $$$i$$$-th line.

Output

Print the answer as an integer.

Example
Input
2 3
2 -1 -1
1 0 2
Output
16
Note

The green circle is the cupcake bread. The other two circles are the frostings. If we count the number of integer points of the green circle that also lie in a frosting circle, we have 11 points in the red circle and 5 in the blue circle.

D. Spicy Cupcakes
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Emily is starting a hip new bakery that serves spicy cupcakes. In fact, she wants her cupcakes to be the spiciest in town! To come up with the optimal lineup for the town's spicy cupcake competition, she has enlisted your help.

Emily's shop sells $$$N$$$ types of cupcakes, the $$$i^\text{th}$$$ of which has an associated spiciness $$$s_i$$$. The judge of the spicy cupcake competition will eat one of each of the types of cupcakes. If the judge has eaten $$$j$$$ cupcakes so far (initially, $$$j = 0$$$), then eating a cupcake with spiciness $$$s$$$ will increase the "cumulative spiciness" value that the judge tallies by $$$$$$(j + 1) \cdot (A \cdot s + B)$$$$$$ where $$$A$$$ and $$$B$$$ are what are known as "cupcake constants".

Emily really wants the judge to feel the heat so that her cupcakes can be deemed the spiciest in town. She wants you to arrange her cupcakes in a line in such a fashion that maximizes the cumulative spiciness value that the judge tallies after eating one of each type of cupcakes in the specified order.

Input

The first line of input will contain a three space-separated integers $$$N\ \left(1 \leq N \leq 10^5\right)$$$ and $$$A, B\ \left(-10^3 \leq A, B \leq 10^3\right)$$$ representing the number of types of cupcakes that Emily's bakery sells as well as the two "cupcake constants", respectively.

The second line of input will contain $$$N$$$ space-separated integers $$$s_i\ \left(1 \leq s_i \leq 10^3\right)$$$ representing the spiciness of the $$$i^\text{th}$$$ type of cupcake that Emily's bakery sells for each $$$i \in \{1, 2, \dots, N\}$$$.

Output

Output a single integer which represents the maximum cumulative spiciness value of Emily's cupcakes attainable across all possible orderings of her cupcake types.

Examples
Input
3 1 1
3 5 8
Output
43
Input
4 2 4
10 10 10 10
Output
240
Note

In the first sample test case, one possible ordering would be $$$(5, 8, 3)$$$, which would yield a cumulative spiciness value of $$$(0 + 1) \cdot (1 \cdot 5 + 1) + (1 + 1) \cdot (1 \cdot 8 + 1) + (2 + 1) \cdot (1 \cdot 3 + 1) = 19$$$.

In the second sample test case, all possible orderings yield the same cumulative spiciness value of $$$(0 + 1) \cdot (2 \cdot 10 + 4) + (1 + 1) \cdot (2 \cdot 10 + 4) + (2 + 1) \cdot (2 \cdot 10 + 4) + (3 + 1) \cdot (2 \cdot 10 + 4) = 240$$$.

E. Cupcake Collecting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice has been teleported into Cupcakeland! Before returning home, she wants to make the most out of her stay by collecting as many cupcakes as possible.

Cupcakeland is represented by a $$$N$$$ x $$$N$$$ grid ($$$1 \leq N \leq 1000$$$), and Alice starts out at the top left corner of the grid. The exit to Cupcakeland is located at the bottom right corner of the grid.

Each remaining square in the grid either contains a $$$-1$$$, denoting an impenetrable tree, or an integer $$$k$$$ ($$$0 \leq k \leq 1000$$$), denoting the number of cupcakes in that square. It is guaranteed that the start and exit squares have 0 cupcakes.

As Alice makes her way to the exit, she will gather all cupcakes that she encounters. Additionally, since she doesn't want to get lost in Cupcakeland, she will only move either downwards or rightwards (towards the exit). Remember that she cannot pass through cells with $$$-1$$$ since they are impenetrable. Please help Alice figure out how many cupcakes she can collect if she chooses the optimal route. If it is impossible for Alice to make it to the exit, please output $$$-1$$$.

Input

The first line of the input contains an integer $$$N$$$.

The next $$$N$$$ lines of the input contain $$$N$$$ space-separated integers, representing the grid.

Output

Please output a single integer, denoting the maximum number of cupcakes Alice can collect on her way out. If it is impossible for her to reach the exit, please output $$$-1$$$.

Examples
Input
4
0 2 3 9
15 0 4 5
0 -1 -1 0
9 0 1 0
Output
25
Input
4
0 2 3 9
15 0 4 5
0 -1 -1 -1
9 -1 1 0
Output
-1

F. Cupcake Circle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Suzie the Cupcake Monster just pulled off a huge heist of $$$n$$$ cupcakes from the Cupcake Factory, with the $$$i$$$th cupcake having a deliciousness of $$$a_i.$$$ To celebrate, she plans to play a game as she eats her cupcakes.

Suzie will first arrange her cupcakes among $$$n$$$ equally spaced indices in a circle. Then, she will start at the first index and begin stepping along the indices of the circle in increasing order, with index $$$n$$$ wrapping around to $$$1$$$. Each time she reaches an index (including the index she starts at), Suzie may choose to eat the cupcake at that index if there is one. To make the game interesting, Suzie wants to eat all of the cupcakes in nondecreasing order of deliciousness (note this means for some cupcakes, she may need to skip over it at first and circle around to eat it later).

Suzie is growing hungry, so she wants to know, for a possible arrangement of her cupcakes, what is the minimum number of steps she must take if she wants to be able to eat all of the cupcakes in nondecreasing order of deliciousness?

Input

The first line contains $$$t$$$ $$$(1\leq t \leq 10^4)-$$$ the number of test cases.

The first line of each test case contains an integer $$$n$$$ $$$(1\leq n \leq 2\cdot 10^5)-$$$ the number of cupcakes.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\dots, a_n$$$ $$$(1\leq a_i\leq 10^9)$$$, where $$$a_i$$$ is the deliciousness of the cupcake at index $$$i$$$ in the circle.

It is guaranteed the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output an integer, the minimum number of steps Suzie must take to eat all of the cupcakes in nondecreasing order of deliciousness.

Example
Input
3
5
1 2 3 4 5
5
1 4 4 2 3
1
100
Output
4
7
0
Note

For the first test case, Suzie can eat each cupcake in order of indices 1, 2, 3, 4, 5, so she just needs to take four steps to reach index 5, eating all the cupcakes as she goes.

For the second test case, Suzie can eat the cupcakes in order of indices 1, 4, 5, 2, 3, which requires her to take seven steps and wrap around the circle once, ending at index 3.

For the third test case, Suzie can eat the only cupcake without taking any steps.

G. Sneaking Sprinkles
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice is preparing cupcakes for a bake-sale! She has $$$N$$$ cupcakes, each with $$$A_i$$$ sprinkles initially on them. She is almost finished decorating the cupcakes, she just has to add $$$N$$$ more layers, each with $$$B_i$$$ sprinkles, to every cupcake. She cannot change the order in which she adds the layers. Unbeknownst to Alice, Bob loves sprinkles and hopes to take some off the cupcakes without her noticing. In fact, every time Alice adds a layer of sprinkles to the cupcakes, Bob will go to the cupcake with the most sprinkles on it and take half of its sprinkles for himself (rounded down). If Bob repeats this process after every layer of sprinkles is added, how many total sprinkles will there be left on Alice's cupcakes?

Input

The first line of input contains an integer $$$N$$$, the number of cupcakes and the number of sprinkle layers to add. The second line of input will contain the array $$$A$$$ with $$$N$$$ values, the initial amount of sprinkles on the $$$i-th$$$ cupcake. The third line of input will contain the array $$$B$$$ with $$$N$$$ values, the number of sprinkles added on the $$$i-th$$$ layer.

$$$ 1 \leq N \leq 5 \cdot 10^4 $$$ , $$$ 1 \leq A_i \leq 10^9 $$$ , $$$ 1 \leq B_i \leq 10^9 $$$

Output

Output a single integer, the total number of sprinkles left on Alice's cupcakes

Example
Input
4
1 2 9 12
3 2 6 4
Output
54
Note

After Alice adds the first layer, the cupcakes have 4, 5, 12, and 15 sprinkles respectively. Then Bob takes 7 sprinkles from the 4th cupcake. Then Alice adds 2 sprinkles to every cupcake, etc.

H. Packing Cupcakes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Strawberry Shortcake is packing cupcakes for her friend Blueberry Tallcake. Shortcake has three different flavors of cupcakes: strawberry, blueberry, and pineberry. She has a $$$N \times M$$$ dimension cupcake container, initially empty, and will place cupcakes into empty spots one-by-one until the container is full.

As Shortcake places cupcakes into the container, she observes the formation of regions of the same cupcake flavor. She formally defines a single 'region' as a maximal connected group of cupcakes of the same flavor, where two cupcakes are considered connected if they are orthogonally adjacent to each other or there is a chain of adjacent cupcakes from one to the other. Shortcake is curious and wonders how many distinct regions exist in the container after each cupcake is placed.

Input

The first line of input contains $$$N,\ M,\ (1 \leq N, M \leq 300)$$$, the number of rows and columns in the cupcake container.

The next $$$N \times M$$$ lines each contain $$$i,\ j,\ f\ (1 \leq i \leq N,\ 1 \leq j \leq M)$$$ meaning Shortcake places a cupcake of flavor $$$f = $$$ S, B, or P (strawberry, blueberry, or pineberry) at position $$$(i, j)$$$ in the container.

Output

For each cupcake that Shortcake places, output the number of distinct regions that exist in the container after she places the cupcake.

Examples
Input
2 2
2 1 P
1 2 P
2 2 S
1 1 P
Output
1
2
3
2
Input
2 3
1 3 S
1 2 P
1 1 P
2 1 P
2 2 B
2 3 B
Output
1
2
2
2
3
3
Input
3 3
2 3 B
3 1 P
3 2 S
1 1 B
3 3 S
1 2 B
1 3 B
2 2 P
2 1 P
Output
1
2
3
4
4
4
3
4
3
Note

I. Cupcake Factory
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Sally just began her new job as a security guard at the Cupcake Factory! Her first task is to transport a cupcake from one side of the factory to the other.

The Cupcake Factory can be represented by a $$$n \times m$$$ grid. ($$$1 \leq n, m \leq 10^3$$$)

Each cell in the grid contains either nothing, a switch, a conveyor, or a wall. If a cell contains a conveyor, the conveyor may be oriented in any of the four cardinal directions.

Initially, all conveyors are off, and any time Sally visits a cell with a switch, she may decide to turn all conveyors on or off, without taking any time.

At each second, if Sally is standing on a conveyor which is currently on, she must move in the direction that the conveyor is facing, taking one second to move between the two cells. If the cell that Sally would move to is a wall or it is outside of the grid, she will be stuck indefinitely, and cannot move any further. Otherwise, she may move in any of the four cardinal directions as long as the corresponding adjacent cell does not contain a wall and is within the grid. This move will take two seconds.

Sally begins at the top-left cell of the grid, and wants to carry a cupcake to the bottom-right cell of the grid, but the cupcake might expire if she takes too long, so she wants you to determine the fewest number of seconds it will take for her to travel from the top-left to the bottom-right of the grid.

Input

The first line of input contains an integer $$$t$$$ denoting the number of testcases. ($$$1 \leq t \leq 10^4$$$)

For each testcase, the first line will contain integers $$$n$$$ and $$$m$$$. ($$$1 \leq n, m \leq 10^3$$$)

The next $$$n$$$ lines will each describe a row of the grid. Each line will consist of a string of $$$m$$$ characters, where the $$$j$$$th character of the $$$i$$$th of these lines denotes the type of cell in the $$$i$$$th row and $$$j$$$th column of the grid. For each character in the string:

  • If this character is '.', then the corresponding cell is empty.
  • If this character is '>', then the corresponding cell contains a conveyor that is moving rightward.
  • If this character is 'v', then the corresponding cell contains a conveyor that is moving downward.
  • If this character is '<', then the corresponding cell contains a conveyor that is moving leftward.
  • If this character is '^', then the corresponding cell contains a conveyor that is moving upward.
  • If this character is '!', then the corresponding cell contains a switch.
  • If this character is '#', then the corresponding cell contains a wall.

It is guaranteed that the top-left and bottom-right cells in the grid are both empty. It is also guaranteed that there is a path from the top-left cell to the bottom-right cell.

Finally, it is guaranteed that the sum of $$$n \cdot m$$$ across all testcases is at most $$$10^6$$$.

Output

Output the fewest number of seconds it will take Sally to reach the bottom-right cell from the top-left cell.

Example
Input
3
4 5
.#...
.#.#.
.#.#.
...#.
4 5
.#...
!#^#v
.#^#v
...#.
7 7
.#.####
!#^....
v#^###v
v#..!#v
v#^###v
v#^###v
>>^###.
Output
26
22
43