UTPC Contest 03-24-23 Div. 1 (Advanced)
C. Calibration Complications
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Another metric scientists use to determine planethood is the mass of the celestial object. Notably, a planet has to be massive enough to be the defining object in its orbit.

Measuring the mass of a planet is a lot harder than measuring its size, since a planet's density can vary widely. Scientists have been using a specialized tool to measure Pluto's mass, but they've discovered that the tool is faulty, and hasn't be calibrated in decades!

They need your help to re-calibrate the tool. You'll be given two rows of diodes, represented by arrays. In a single operation, you can add 1 to any value in the first array. Alternatively, in a single operation, you can subtract 1 from any value in the second array. You want to minimize the number of operations you make. How many operations are required to make all values in both arrays equal? Output -1 if this is not possible.

The fate of Pluto depends on it!

Input

The first line contains a single integer $$$N$$$ ($$$1 \le N \le 10^5$$$), the length of the two arrays.

The second line contains $$$N$$$ integers $$$a_1, a_2, ..., a_N$$$ ($$$1 \le a_i \le 10^9$$$), the values for the first array.

The third line contains $$$N$$$ integers $$$b_1, b_2, ..., b_N$$$ ($$$1 \le b_i \le 10^9$$$), the values for the second array.

Output

Print out a single integer, the number of operations required to make all values in both arrays equal, or output -1 if this is not possible. This integer may not fit in a standard 32-bit integer, so make sure you are using 64-bit integers!

Example
Input
3
1 2 3
4 5 6
Output
9

D. Celestial Sky
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The sky is draped in an invisible coordinate system that will help you find your way anywhere in the universe. Your telescope shows a slice of the sky that resembles this coordinate system, and in it contains a series of $$$N$$$ stars. Note that the coordinates of stars may overlap. You would like to count all the stars within a certain rectangular region in the coordinate system. But, there is a catch. If you detect a black hole, you know that they will eat up everything in the 3x3 box centered at their starting coordinate, so any stars in the vicinity will cease to exist in another 100 million years. Given that you want your stars to be intact in the next 100 million years, please figure out how many such stars are in your query box.

Input

The first line of input contains the positive integers $$$N$$$, $$$M$$$, and $$$Q$$$ ($$$1 \leq N,M,Q \leq 10^5$$$).

The next $$$N$$$ lines each contain two integers $$$x, y$$$ ($$$0 \leq x, y \lt 1000$$$), describing the (not necessarily distinct) coordinates of a star.

The next $$$M$$$ lines each contain two integers $$$x,y$$$ ($$$0 \leq x, y \lt 1000$$$), describing the coordinates of a black hole.

The last $$$Q$$$ lines contain four integers $$$x_1,y_1,x_2,y_2$$$ ($$$0 \leq x_1, y_1, x_2, y_2 \lt 1000$$$), describing the lower-left $$$(x_1,y_1)$$$ and upper-right $$$(x_2,y_2)$$$ corner of the rectangle, which has positive area.

Output

Please output $$$Q$$$ lines, the $$$i$$$-th line containing the number of valid stars in the $$$i$$$-th query rectangle.

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

Note that star and black hole coordinates may overlap, and are not necessarily distinct.

E. Gluing Pluto Back Together
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Luna is a space explorer who has spent the last few years traveling through the vast expanse of the universe in search of new and exciting discoveries. She has visited countless planets, but her most recent find is one that has truly captivated her.

Luna has just discovered a number of space rocks and would like to form a new planet by gluing them in a ring. Specifically, she has found $$$N$$$ pieces of rock numbered from $$$1$$$ to $$$N$$$. Luna's mission is to glue the rocks together to form the planet. However, the cost of gluing each pair of adjacent rocks varies.

Luna has gathered data on the costs for each pair of rocks and is now faced with the challenge of building the planet while minimizing the overall cost. Gluing rocks $$$i$$$ and $$$j$$$ together costs $$$C_{i,j} = C_{j,i}$$$.

In order to minimize the cost of building the planet, Luna needs to find the optimal order in which to glue the rocks. She must ensure that the sequence of rocks forms a connected cycle. Your task is to help Luna determine the minimum cost to build this new ring planet.

Input

The first line of input contains an integer $$$N$$$ $$$(2 \leq N \leq 12)$$$ - the number of rocks on the planet.

Each of the next $$$N$$$ lines contains $$$N$$$ integers representing the cost to glue each rock to the other rocks. Each cost is a non-negative integer not exceeding $$$10^5$$$.

Output

Output a single integer - the minimum cost to build the planet.

Example
Input
4
0 1 2 3
1 0 4 5
2 4 0 6
3 5 6 0
Output
14

F. Plutonian Hot Dog Stand
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mike runs a hot dog stand on Pluto. There are $$$N$$$ Plutonians in line to buy hot dogs and the $$$i^{th}$$$ Plutonian wants to buy $$$M_i$$$ hot dogs. Mike also has $$$D$$$ discount tickets which he wants to distribute among the Plutonians. Each Plutonian can have at most $$$1$$$ discount ticket. If Mike chooses to give a discount ticket to the $$$i^{th}$$$ Plutonian, all consecutive $$$j$$$ Plutonians after the $$$i^{th}$$$ Plutonian where $$$M_j \leq M_i$$$ will also get a discount.

Mike is feeling nice today and wants as many people to get discounts as possible. Please help Mike find the maximum number of people who can get a discount if he distributes the $$$D$$$ discount tickets optimally.

Input

The first line of input contains the integers $$$N \space D$$$. $$$(1 \leq N \leq 10^5, \space 1 \leq D \leq \min(N, 100))$$$

The next line contains $$$N$$$ integers where the $$$i^{th}$$$ integer represents $$$M_i$$$. $$$(1 \leq M_i \leq N)$$$

Output

Please output one integer, the maximum number of people who can get a discount.

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

$$$\textbf{For sample test case #1}$$$:

There are 8 Plutonians in line. We have 2 discount tickets to distribute.

We can give the 1st ticket to the 5th Plutonian in line. Then, all Plutonians after (6th, 7th, and 8th) also get a discount. We can give the 2nd ticket to the 3rd Plutonian. Then, the 4th Plutonian will also receive a discount. Thus, a maximum of 6 Plutonians can get a discount.

$$$\textbf{For sample test case #2}$$$:

No matter how we distribute the 3 discount tickets, no other Plutonians in line will benefit from additional discounts.

$$$\textbf{For sample test case #3}$$$:

Mike can give the 1st ticket to the 1st Plutonian. Then, every other Plutonian in line will get a discount, regardless of how he distributes the other 2 tickets. Thus, all 10 Plutonians get a discount.

G. Path to Pluto
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In celebration of the 300th anniversary of the naming of Pluto, the Plutonian government is hosting a massive event. Pluto was just one of many planets to eventually be discovered, and by now there are $$$n$$$ ($$$2 \leq n \leq 10^5$$$) planets in the solar system. Pluto is planet $$$1$$$. There are also currently $$$n - 1$$$ unidirectional roads between planets. Each road leads from one planet to another, and each road also has a fee for traveling across.

For each planet $$$i$$$ ($$$1 \leq i \leq n$$$), its travel cost $$$t_i$$$ is the minimum cost over all paths from planet $$$i$$$ to Pluto (planet $$$1$$$). The Plutonian government wants to minimize the sum of the travel cost over all planets, and to help, they can afford to construct at most one new road between any two planets with cost $$$C$$$. Please help the Plutonian government decide where to construct one road in order to minimize the sum of all travel costs.

Input

The first line of input contains integers $$$N$$$ and $$$C$$$. ($$$2 \leq N \leq 10^5$$$, $$$1 \leq C \leq 10^6$$$) These represent the number of planets and the travel fee on the additional road repectively.

The next $$$n - 1$$$ lines each contain integers $$$u_i$$$, $$$v_i$$$, and $$$c_i$$$ ($$$1 \leq u_i, v_i \leq N$$$, $$$1 \leq c_i \leq 10^6$$$), where $$$u_i$$$ and $$$v_i$$$ represent the start and end of the $$$i$$$th road respectively, and $$$c_i$$$ represents the fee for traveling across the road.

It is guaranteed that Pluto is reachable from all planets.

Output

The output should consist of a single integer representing the minimum sum of travel costs after adding at most one road. Note that the Plutonian government can decide not to add a road.

Examples
Input
4 2
2 1 4
3 1 8
4 1 6
Output
12
Input
5 2
2 1 3
3 1 10
4 3 5
5 3 6
Output
20
Input
8 255
2 1 320
5 1 345
7 5 590
4 2 110
3 2 290
6 5 235
8 1 915
Output
3455
Note

In the first test case, we can add the edge from planet $$$1$$$ to planet $$$3$$$, which makes the sum of all travel costs $$$0 + 4 + 2 + 6 = 12$$$. It can be proven that no other placement of the extra road can minimize this further.

H. Plantery Observations
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the 4th century BC, Edwin observes a point in the sky and notices that all the planets in their solar system cross by this point at various points in time. Every time he sees a planet cross by this point, he logs this in his journal.

Being smart, Edwin decides to invent the computer and wants to write a program to help him determine the smallest period that could explain his observations $$$O$$$ in the sky.

There are two kinds of queries Edwin wants to give the computer:

  • 0 s where Edwin writes down a string $$$s$$$ of $$$len(s)$$$–these observations which get appended to a string $$$O$$$
  • 1 Edwin wants to know the smallest period that could explain his observations in the sky.

It is guaranteed that $$$N\cdot \sum len(s)\leq 2\cdot 10^5$$$ and the first query is of type $$$0$$$.

Input

The first line will contain $$$N (1\leq N\leq 10^3)$$$, the number of queries.

The next $$$N$$$ lines will either contain a query either of type 0 s or 1.

Output

For each query of type 1, print out the smallest period that could explain his observations in the sky on a new line.

Examples
Input
2
0 abcabca
1
Output
3
Input
4
0 ab
1
0 cabca
1
Output
2
3

I. Wormholes
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Meryl and Roberto are currently on planet Gunsmoke and are trying to reach Pluto. They each leave Gunsmoke in a one-person space pod, and the only way they can travel between planets is by traveling through wormholes located around each planet. However, these wormholes highly unstable. Each wormhole can only be taken once before it collapses. Additionally, each wormhole causes a certain amount of damage to the space pod. Finally, wormholes only go in one direction. Due to the laws of physics, there cannot be multiple wormholes that start at the same planet and go to the same planet. Meryl and Roberto want to know whether it is possible for both of them to reach Pluto, and if so, what the least amount of total damage they can take on their way to Pluto.

Input

The first line contains $$$n$$$ ($$$2 \leq n \leq 2 \times 10^5$$$), the number of planets, and $$$m$$$, ($$$1 \leq m \leq 2 \times 10^5$$$) the number of wormholes. Planet 1 is Gunsmoke, and planet $$$n$$$ is Pluto. The following $$$m$$$ lines each contain an integer $$$a$$$ ($$$1 \leq a \leq n$$$), $$$b$$$ ($$$1 \leq b \leq n$$$), and $$$c$$$ ($$$1 \leq c \leq 10^9$$$). This represents a wormhole from planet $$$a$$$ to planet $$$b$$$ that causes $$$c$$$ damage to a space pod passing through it.

Output

If it is impossible for both Meryl and Roberto to reach Pluto, print out $$$-1$$$. Otherwise, print out the minimum possible total damage received to the two space pods.

Examples
Input
6 14
1 2 1
2 1 1
1 3 2
3 1 2
2 4 1
4 2 1
3 4 2
4 3 2
2 5 2
5 2 2
4 6 1
6 4 1
5 6 2
6 5 2
Output
10
Input
5 7
2 5 5
2 4 3
1 4 2
4 5 10
4 2 7
1 3 5
3 2 1
Output
23
Input
5 5
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
Output
-1

J. Rocket Fuel
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Your preparations to visit Pluto have been going as planned, and you are ready to launch the rocket! All you need to do is calculate how much fuel is required. There are $$$n$$$ engines on the ship, and engine $$$i$$$ requires $$$f_{t, i}$$$ fuel at time $$$t$$$. You know the initial amount of fuel required, $$$f_{1, i}$$$, for each engine.

As time goes on, more and more fuel is required. Between times $$$t$$$ and $$$t + 1$$$, engines $$$l_t$$$ through $$$r_t$$$ require $$$d_t$$$ more fuel. In other words, the update is as follows: $$$$$$ f_{t + 1, i} = \begin{cases} f_{t, i} + d_t & \text{if $l_t \leq i \leq r_t$} \\ f_{t, i} & \text{otherwise} \end{cases} $$$$$$

As part of the fuel calculations, you want to answer $$$q$$$ queries about the fuel. Query asks for the total amount of fuel used by engines $$$ql_i$$$ through $$$qr_i$$$ between times $$$a_i$$$ and $$$b_i$$$. Can you answer each of the queries?

Input

The first line of the input contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$1 \leq n, m, q \leq 2 \cdot 10^5$$$) — the number of engines, the number of updates, and the number of queries, respectively.

The next line contains $$$n$$$ space-separated integers $$$f_{1, 1}, f_{1, 2}, \dots, f_{1, n}$$$ ($$$0 \leq f_{1, i} \leq 10^5$$$) — the initial fuel required for each engine.

The next $$$m$$$ lines contain the $$$m$$$ updates. Each of these lines contains three integers $$$l_i$$$, $$$r_i$$$, and $$$d_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$, $$$1 \leq d_i \leq 10^5$$$) — the leftmost engine updated at this time, the rightmost engine updated at this time, and how much more fuel each engine requires, respectively.

The next $$$q$$$ lines contain the $$$q$$$ queries. Each of these lines contains four integers $$$ql_i$$$, $$$qr_i$$$, $$$a_i$$$, and $$$b_i$$$ ($$$1 \leq ql_i \leq qr_i \leq n$$$, $$$1 \leq a_i \leq b_i \leq m + 1$$$) — the leftmost engine queries, the rightmost engine queried, the earliest time queried, and the latest time queried, respectively.

Output

Output $$$q$$$ integers representing the answer to each query in the order given in the input.

Example
Input
4 2 3
1 2 3 4
1 3 1
2 4 3
1 4 1 3
2 2 2 2
3 4 2 3
Output
45
3
22
Note

Note that the set of possible times that we can query includes time $$$m + 1$$$, which occurs after the final update.

For the sample input, the fuel required for each engine at each time is:

  • $$$t = 1$$$: $$$[1, 2, 3, 4]$$$
  • $$$t = 2$$$: $$$[2, 3, 4, 4]$$$
  • $$$t = 3$$$: $$$[2, 6, 7, 7]$$$