UTPC Contest 09-16-22 Div. 2 (Beginner)
A. Truck Driver
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are a truck driver and have been given $$$n$$$ boxes. Your boss wants to know what the $$$k^{th}$$$ heaviest box weighs.

Input

The first line will contain the integer $$$k$$$ (($$$1 \leq k \leq 10^5$$$). The second line of input will contain $$$n$$$ integers ($$$1 \leq n \leq 10^5$$$) containing the weights of each of the $$$n$$$ boxes. Each box has a weight $$$w$$$ where ($$$1 \leq w \leq 10^5$$$) and all weights are distinct.

Output

Output the $$$k^{th}$$$ heaviest box's weight.

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

B. Anya's Rocks
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Anya has a row of $$$N$$$ rocks that are each painted one of $$$C$$$ possible colors. Although Anya likes all kinds of rocks, she will throw a fit if two adjacent rocks have the same color. She wants to select the longest possible contiguous subsequence of rocks in the row such that no two adjacent rocks have the same color. Can you help our heroine find the longest segment with this property?

Input

The first line contains two integers $$$N$$$ and $$$C$$$ ($$$1 \leq N, C \leq 100$$$), representing the number of rocks and the number of colors, respectively. The next line contains $$$N$$$ space-separated integers $$$c_i$$$ ($$$1 \leq c_i \leq C$$$) which denote the colors of the rocks along the row.

Output

Output a single integer representing the maximum number of rocks on the segment having no two adjacent rocks with the same color.

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

We can select contiguous subsequence [4 1 2 3] in the sample test case.

C. Earthbending years
time limit per test
1 second
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.