UTPC Contest 09-16-22 Div. 1 (Advanced)
C. Earthbending years
time limit per test
1 с
memory limit per test
256 megabytes
input
standard input
output
standard output

It is Earth Kingdom tradition to track the year with some piles of raised earth. To mark the new year, earthbenders come together to raise the ground $$$1$$$ unit, representing the new year.

Unfortunately, they can only raise the dirt from its initial height of $$$0$$$ to a maximum height of $$$3$$$ (since they lack proper training). As a solution, when a pile needs to be raised to a height of $$$4$$$, instead they gently lower the pile back to a height of $$$0$$$ and raise the area to the right by $$$1$$$ unit of height.

There are currently $$$N$$$ piles, representing the current year. Given the state of the dirt piles, determine what the piles would look like in $$$K$$$ years.

Input

Two space-separated numbers, $$$1 \leq N \leq 1000$$$ and $$$1 \leq K \leq 10^4$$$.

The next $$$N$$$ numbers represent the current pile heights from left to right, where the last pile is guaranteed to have non-zero height.

Output

The piles after $$$K$$$ years, from left to right, where the last pile has non-zero height.

Examples
Input
3 6
3 2 2
Output
1 0 3 
Input
1 21
2
Output
3 1 1 

D. Coats of Paint
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For National Rock Day, you've decided to paint the rock that you were gifted. This is a peculiar rock that is divided into $$$n$$$ sections, numbered $$$1,...,n$$$. Every second for the next $$$x$$$ seconds, your friend will give you two numbers. The first number will represent the section that you should start painting at and then the second number will represent the section that you should stop painting at (both inclusive). Every coat of paint will have a thickness of 1. Can you find the section with the largest thickness at any point in the rock after all layers of paint have been applied?

Input

The first line contains one number $$$n$$$ ($$$1 \leq n \leq 10^5$$$), representing the number of sections the rock is divided into. The second line contains one number $$$x$$$ ($$$1 \leq x \leq 100$$$), representing the number of times your friend will give you starting and stopping numbers.

The next $$$x$$$ lines will each contain two integers $$$i, j$$$ ($$$1 \leq i \leq j \leq n$$$) representing the starting and stopping sections to paint.

Output

Output the region of the rock that has the greatest thickness (has the most coats of paint). If there are multiple, return the lowest section number.

Examples
Input
5
1
2 4
Output
2
Input
10
3
3 5
4 8
5 9
Output
5

E. It's Raining Rocks!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It's raining rocks! Hallelujah!

It's raining rocks, every type of rock!

Pyroclastic, metamorphic, lustrous, and igneous!

Coarse and silty and sedimentary and porous!

Specifically, it's raining rocks in $$$N$$$ very specific locations along a line, where the $$$l_i$$$ is the $$$i$$$-th location. Before the weather event, you want to set up a system to collect these rocks to avoid catastrophic landslides. You plan to lay out some baskets where the rocks will fall, to keep them contained.

A basket of width $$$w$$$ can capture rocks from $$$w$$$ consecutive locations. You have commissioned $$$K$$$ baskets with the same width, but you still need to figure out how wide the baskets should be.

Given the locations of rock-rain, $$$l_i$$$ and the number of commissioned baskets, determine the minimal width the baskets should be to capture every falling rock.

Input

The first line contains two integers, $$$1 \leq N \leq 10^5$$$ and $$$1 \leq K \leq 10^5$$$.

The second line contains $$$N$$$ integers, $$$1 \leq l_i \leq 10^9$$$

Output

Output a single number, the minimal basket width needed to collect all the rocks.

Example
Input
4 2
6 1 4 5
Output
3

F. Bit Paths
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ cities in BIT Land, where the $$$i$$$th city has value $$$a_i$$$. Between every pair of cities, there is a road paved with rocks. The cost to travel from city $$$i$$$ to city $$$j$$$ over the rocky road is $$$a_i \& a_j$$$, where $$$\&$$$ is the bitwise AND operator.

Some of these distances are large, so you discovered an alternative route. Each city $$$i$$$ has a corresponding city in the mirror universe TIB Land. The value of each city in TIB Land, $$$b_i$$$, is the value you get when flipping the lowest $$$32$$$ bits of $$$a_i$$$. Between each pair of cities is a road paved with avocados. The cost to travel from city $$$i$$$ to city $$$j$$$ over the avocado-y road is $$$b_i \& b_j$$$. There is a portal between city $$$i$$$ in BIT Land and city $$$i$$$ in TIB Land, so there is no cost traveling between the two universes.

You want to make a delivery of rocks and avocados starting at city $$$1$$$ and ending at city $$$n$$$, both in BIT Land. You want to minimize the total cost of your path, which is computed by summing the cost of each edge you travel on. What is the minimum cost that you would have over any path?

Input

The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 2000$$$) — the number of cities.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 2^{32} - 2$$$) – the value of each city in BIT Land.

Output

Print a single integer — the shortest distance from city $$$1$$$ in BIT Land to city $$$n$$$ in BIT Land.

Examples
Input
3
1 2 1
Output
0
Input
2
4294967294 4294967292
Output
1

G. Magnetic Backpack
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Everyone loves collecting rocks! That is, everyone except you.

You are stuck in a big cave, with your trusty magnetic backpack. The cave consists of $$$n$$$ caverns connected by $$$m$$$ tunnels. You start at cavern $$$1$$$ and the exit as at cavern $$$n$$$. Each tunnel has $$$a$$$ magnetic rocks that will automatically stick to your backpack once you enter the tunnel. However, each tunnel also has its own magnetic field, and will take away $$$b$$$ rocks once you leave (or all of your rocks, if you have less than $$$b$$$ rocks).

You hate collecting rocks, so you must figure out how to leave with the least number of rocks, if you even can escape this cave.

Input

The first line contains two integers, $$$n$$$ ($$$1 \leq n \leq 300$$$) and $$$m$$$ ($$$1 \leq m \leq n(n-1)$$$).

Then, $$$m$$$ lines follow, each containing four integers: $$$x$$$, $$$y$$$ ($$$1 \leq x, y \leq n$$$) and $$$a$$$, $$$b$$$ ($$$0 \leq a, b \leq 10$$$). This denotes a one-way tunnel from cavern $$$x$$$ to cavern $$$y$$$, where you gain $$$a$$$ rocks upon entering and lose $$$b$$$ rocks upon leaving.

Output

Output a single integer, the minimum number of rocks you can leave the cave with, or -1 if it is not possible to escape the cave.

Example
Input
4 4
1 2 10 0
2 4 2 1
4 3 0 5
3 2 3 3
Output
1
Note

In the example, a path that achieves this is 1 -> 2 -> 4 -> 3 -> 2 -> 4 -> 3 -> 2 -> 4 -> 3 -> 2 -> 4. In order, the number of stones you have is: 0, 10, 11, 6, 6, 7, 2, 2, 3, 0, 0, 1.

H. Rocks & Fossils Kit - 200+ Piece Set
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Jackson School of Geosciences recently bought a Rocks & Fossils Kit – 200+ Piece Set Includes Geodes, Real Fossils, Rose Quartz, Jasper, Aventurine & Many More Rocks, Crystals & Gemstones! The school would like to give out the rocks to faculty. To do so, they lay out the rocks in a line. Each rock has some value $$$c_i$$$.

However, as geologists specializing in different rock types, the faculty members have very particular requirements as to what rocks they are willing to take. In particular, each geologist will only take rocks starting at some position $$$a_j$$$, and then continue taking rocks from indices $$$a_j+1, a_j+2,...$$$ until one of the following happens:

  • The rock at the new index has already been taken.
  • They reach the end of the line.
  • They satisfy their collection, that is, the total value of the rocks they've taken so far is greater than or equal to some value $$$k_j$$$.

The faculty members line up to take turns choosing rocks. JSC wants to know: what's the maximum number of collections that can be satisfied, if they choose the optimal order in which the faculty members line up?

Input

The first line contains two integers $$$1 \le N \le 10^5$$$ and $$$1 \le M \le 10^5$$$, corresponding to the number of rocks and the number of faculty members, respectively.

The next line contains $$$N$$$ integers $$$c_1,...,c_N$$$, where $$$c_i$$$ represents the value of the $$$i$$$th rock. $$$(1 \le c_i \le 10^9)$$$

The third line contains $$$M$$$ integers $$$a_1,...,a_M$$$, where the $$$j$$$th faculty member takes rocks starting at index $$$a_j$$$. $$$(1 \le a_j \le N)$$$

The fourth and final line contains $$$M$$$ integers $$$k_1,...k_M$$$, where the $$$j$$$th faculty member satisfies their rock collection if the total value of the rocks they collect is greater than or equal to $$$k_j$$$. $$$(1 \le k_j \le 10^9)$$$

Output

Output one integer: the maximum number of collections that can be satisfied.

Examples
Input
7 4
1 5 3 1 2 3 1
1 3 4 5
5 6 5 6
Output
2
Input
7 3
1 5 3 3 2 3 1
1 2 5
10 1 3
Output
2
Note

In the first example, one possible ordering of faculty members is [1, 3, 2, 4]:

  • The first faculty member takes the 1st and 2nd rocks to satisfy their collection ($$$1 + 5 \ge 5$$$).
  • The third faculty member takes the 4th, 5th, and 6th rocks to satisfy their collection ($$$1 + 2 + 3 \ge 6$$$).
  • The second faculty member takes the 3rd rock, but the 4th rock has already been taken, so they can't satisfy their collection ($$$3 \lt 5$$$).
  • The fourth faculty member can't satisfy their collection because the 5th rock has already been taken. ($$$0 \lt 6$$$)
Note that other orderings are possible, but none can satisfy more than two collections.

I. Cabinet Search
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Bernardo just made an amazing lunch for himself, featuring his favorite dish, guacamole! He used a slew of ingredients along with his trusty molcajete, but now its time for him to clean up the mess he made while cooking. He has to hurry, though, in order to make it on time to his job (as a truck driver who transports large amounts of rocks and avocados across the country).

Because he is short on time, Bernardo needs to be efficient as he cleans up, so he will only perform $$$Q$$$ actions to tidy his kitchen.

Bernardo has $$$N$$$ cabinets in his kitchen lined up in a row. Initially, they are all closed, and can contain zero or more ingredients. For each integer $$$i$$$ such that $$$1 \leq i \leq Q$$$, Bernardo will perform an action, either:

  • $$$1$$$ - Open the $$$x_i$$$th cabinet (it is guaranteed that the $$$x_i$$$th cabinet will be closed before this action).
  • $$$2$$$ - Swap the number of ingredients in the $$$x_i$$$th and $$$y_i$$$th cabinets (these cabinets need not be open).
  • $$$3$$$ - Add $$$y_i$$$ ingredients to the $$$x_i$$$th cabinet (this cabinet need not be open).
  • $$$4$$$ - Move all ingredients from the $$$x_i$$$th cabinet to the $$$y_i$$$th cabinet (these cabinets need not be open).

After each of the $$$Q$$$ actions, your task is to calculate the length of the longest contiguous subarray of open cabinets as well as the maximum sum of the number of ingredients found within any contiguous subarray of open cabinets.

Input

The input will begin with a line containing two space separated integers, $$$N$$$, and $$$Q$$$ ($$$1 \leq N, Q \leq 10^5$$$).

The next line will contain $$$N$$$ space separated integers, the $$$i$$$th of which, denoted by $$$x_i$$$ ($$$1 \leq x_i \leq 10^9$$$), denoting how many ingredients are initially in the $$$i$$$th cabinet.

The next $$$Q$$$ lines will each describe one of Bernardo's action. The $$$i$$$th of these lines will begin with an integer $$$t$$$ ($$$t \in \{1, 2, 3, 4\}$$$), denoting the type of the $$$i$$$th action.

If $$$t = 1$$$, there will also appear a single integer $$$x_i$$$ ($$$1 \leq x_i \leq N$$$), denoting the cabinet to open. If $$$t = 2$$$, there will also appear two integers, $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq N$$$), denoting the cabinets to swap the ingredients of. If $$$t = 3$$$, there will also appear two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i \leq N$$$, $$$1 \leq y_i \leq 10^9$$$), denoting the cabinet to add $$$y_i$$$ ingredients to. Finally, if $$$t = 4$$$, there will also appear two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq N$$$), denoting that all ingredients from $$$x_i$$$ should move to cabinet $$$y_i$$$.

Output

Output should consist of $$$Q$$$ lines, the $$$i$$$th of which containing two space-separated integers. The first should represent the length of the longest contiguous subarray of open cabinets after the $$$i$$$th action, and the second should represent the maximum sum of the number of ingredients found within any contiguous subarray of open cabinets.

Examples
Input
3 3
1 2 3
1 2
2 1 3
1 3
Output
1 2
1 2
2 3
Input
5 5
1 1 1 1 1
1 2
1 4
1 3
1 1
1 5
Output
1 1
1 1
3 3
4 4
5 5

J. Rock Balancing
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Daniel RuLasso has acquired a large circular platform that he intends to place in the middle of a lake, and has a collection of $$$N$$$ equally weighted rocks (treated as points on the 2D plane) that he wishes to arrange on the platform for decoration. He figures that he can kill two birds with one stone by assigning the task to Kobra Cai students. As all the rocks are conveniently already on the platform, Daniel asks the students to move the rocks into a balanced state on the platform for a more aesthetically pleasing setup.

The platform is centered at the origin of the 2D plane and has infinite radius. An arrangement of rocks on the platform is considered balanced if it will not cause the platform to capsize once placed in water; this requires every rock at $$$(x, y)$$$ to be matched with a corresponding rock that is symmetric about the origin (possibly itself). Multiple rocks can be placed at the same location. However, moving any rock from $$$(a, b)$$$ to $$$(c, d)$$$ requires $$$\left(|a-c|^2 + |b-d|^2\right)$$$ energy units. The Kobra Cai students want to minimize the total energy units expended to achieve a balanced arrangement, and would like to know the minimum amount of energy units needed to do so.

Input

The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 20$$$), representing the number of rocks on the platform. The next $$$N$$$ lines of input contain two integers $$$x, y$$$ ($$$0 \leq |x|, |y| \leq 10^4$$$) representing the current position $$$(x, y)$$$ of a rock.

Output

Output the total amount of energy units necessary to move the $$$N$$$ rocks into a balanced arrangement. Any answer within $$$10^{-6}$$$ of the true solution will be accepted.

Examples
Input
2
-1 1
1 1
Output
2.0000000000
Input
1
3 4
Output
25.0000000000
Note

For the first case, both rocks can be moved onto the $$$x$$$-axis.

For the second case, the sole rock just needs to be moved to the origin.