MEPhI Spring Cup 2025
A. Mysterious Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While exploring the ruins of an ancient city, archaeologists discovered a huge wall with an array of non-negative integers $$$a$$$ inscribed on it. After considerable effort, they managed to read the ancient inscriptions and understand that this array could reveal crucial information about the ancient civilization. One of the steps to achieve this is to solve a certain problem related to this array.

You can perform the following operation on the array: choose 2 indices $$$i$$$ and $$$j\, (1 \le i \lt j \le n)$$$, where $$$n$$$ is the length of the array $$$a$$$, and then subtract 2 from $$$a_i$$$ and add 1 to $$$a_j$$$. After each operation, all elements of the array must remain non-negative. You need to determine the maximum number of operations that can be applied to the array $$$a$$$.

Input

The first line contains a single integer $$$n\, (1 \le n \le 10^5)$$$ – the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n\, (0 \le a_i \le 10^9)$$$.

Output

In a single line, output the maximum number of operations that can be performed on the given array $$$a$$$.

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

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

After years of searching, disappointments, and adventures, the treasure hunters found the legendary cave where a huge treasure was supposed to be buried. However, they did not find the treasure here, but only $$$k$$$ keys to chests and a mysterious message. It turned out that the treasure is buried in $$$n$$$ different cities, which are connected by a fast river. In city $$$i$$$, there are $$$a_i$$$ coins hidden.

Currently, the treasure hunters are in city $$$1$$$. To move between cities, they will have to go upstream on their ship. However, they will have to pay $$$c_i$$$ coins to buy coal to get from city $$$i$$$ to city $$$i+1$$$ – there are no other routes between the cities.

The treasure hunters can open no more than $$$k$$$ chests in total, but if they arrive in city $$$i$$$, they do not necessarily have to spend their key on the treasure here. After they stop searching for the treasure, they can return without any coal costs (it can be assumed that going downstream on this river does not require fuel).

It is necessary to determine what maximum profit they can obtain.

Input

The first line contains two integers $$$n, k\, (1 \le k \le n \le 10^5)$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n\, (0 \le a_i \le 10^9)$$$ – the number of coins in each city.

The third line contains $$$n - 1$$$ integers $$$c_1, c_2, \ldots, c_{n-1}, (0 \le c_i \le 10^9)$$$ – the costs of moving from city $$$i$$$ to city $$$i+1$$$.

Output

Print the maximum possible profit.

Examples
Input
5 2
10 3 2 20 45
5 5 5 50
Output
15
Input
7 3
0 0 5 8 13 17 20
9 5 7 10 1 8
Output
10

C. Bumpy Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a small town, hidden from prying eyes in the mountains, archaeologists stumbled upon a mysterious cave. Inside, they discovered ancient manuscripts written in an unknown language. After long studies and deciphering the text, the scholars concluded that the records belong to a well-known civilization that existed thousands of years ago and contain information about a certain mathematical problem. They believe that solving this problem may be important for their research, and therefore ask you to write a program to solve it.

The problem is formulated as follows: an array $$$b$$$ is called bumpy if each of its internal elements (that is, not the first or the last) is strictly greater than or strictly less than both of its neighbors.

Initially, a certain array $$$a$$$ consisting of integers is given. In one operation, you can choose a certain element of the array and increase or decrease it by 1.

You need to determine the minimum number of operations required to make the array $$$a$$$ bumpy.

Input

The first line of input contains one integer $$$n\, (3 \le n \le 10^5)$$$ — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n\, (-10^9\le a_i \le 10^9)$$$ — the values of the elements of the array $$$a$$$.

Output

Output the minimum number of operations required to make the array $$$a$$$ bumpy.

Examples
Input
5
1 3 5 6 5
Output
3
Input
8
-8 4 -6 5 9 -7 8 1
Output
25

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

A group of scientists from MEPhI is working on another experiment. They want to conduct an experiment with various charged particles.

During the experiment, the following types of events may occur:

  • $$$1$$$ $$$x$$$ $$$t$$$ – a new particle of energy $$$x$$$ and type $$$t$$$ appears.
  • $$$2$$$ $$$x$$$ $$$t$$$ – any particle of type $$$t$$$ with energy $$$x$$$ disappears. If there are no such particles, nothing changes.
  • $$$3$$$ $$$x$$$ $$$t$$$ – the energy of all particles of type $$$t$$$ increases by $$$x$$$ units.
  • $$$4$$$ – the sum of the energies of all particles is required to be output.
  • $$$5$$$ – the minimum energy among all particles is required to be output; if there are no particles, output $$$-1$$$.

The experiment may have significant implications for future work, so the scientists ask you to write a program that will verify the correctness of the results.

Input

The first line contains a single integer $$$q\, (1 \le q \le 3 \cdot 10^5)$$$ – the number of queries. Each of the following $$$q$$$ lines contains the next query in the format described above.

It is guaranteed that in each of them $$$1 \le t \le q$$$ and $$$1 \le x \le 10^9$$$, and that all numbers in the input are integers.

Output

For each query of type $$$4$$$ and $$$5$$$, output the required number on a separate line.

Examples
Input
6
2 10 2
5
1 15 1
1 17 2
3 3 1
4
Output
-1
35
Input
17
1 10 1
1 10 2
3 10 1
5
4
1 20 1
2 20 1
5
2 10 1
4
2 30 1
2 20 1
4
5
2 10 2
4
5
Output
10
30
10
30
10
10
0
-1

E. Maze of Time
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A certain laboratory consists of $$$n$$$ rooms connected by $$$m$$$ bidirectional corridors, which require a certain amount of time to traverse. Mysterious experiments with time were conducted in the laboratory, resulting in the discovery that if one follows a certain route and visits some pairs of corridors, the time spent will increase by a certain amount, even though it should not happen at first glance. The chief scientist learned about this and plans to go to the main room of the laboratory $$$n$$$ to fix the anomalies. Initially, he is in room $$$1$$$.

Help him determine the minimum time he needs to reach room $$$n$$$. If it is impossible to get from room $$$1$$$ to room $$$n$$$, output $$$-1$$$.

Input

The first line contains 3 integers $$$n, m$$$, and $$$k\, (1 \le n \le 10^5,\, 1 \le m \le 10^5,\, 0 \le k \le 5)$$$ — the number of rooms in the laboratory, the number of corridors, and the number of pairs of special corridors.

The next $$$m$$$ lines each contain 3 integers $$$u, v$$$, and $$$t$$$, indicating that there is a bidirectional passage between rooms $$$u$$$ and $$$v$$$, which takes $$$t$$$ time to traverse $$$(1 \le u,v \le n,\, 1 \le t \le 10^9)$$$.

Then, in $$$k$$$ lines, there are 3 integers $$$i,\, j$$$, and $$$t\, (1 \le i,j \le m,\, i \ne j,\, 1 \le t \le 10^9)$$$, indicating that if the scientist visits both corridor number $$$i$$$ and corridor number $$$j$$$ (in any order) on the way from $$$1$$$ to $$$n$$$, the time of his journey will increase by $$$t$$$.

It is guaranteed that all $$$2 \cdot k$$$ corridor numbers that increase time are distinct.

Output

In a single line, output the answer to the problem.

Examples
Input
5 6 2
1 2 2
2 3 6
3 5 3
2 5 7
1 4 5
4 5 1
5 6 10
1 3 10
Output
9
Input
5 6 3
1 2 2
2 3 6
3 5 3
2 5 7
1 4 5
4 5 1
5 6 14
1 4 100
2 3 10
Output
20

F. Randomizer
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem

While contemplating various simple pseudo-random number generators, Andrew-13 decided to consider a linear generator characterized by parameters $$$a$$$, $$$b$$$, and $$$p$$$ ($$$1 \le a \lt p$$$, $$$0 \le b \lt p$$$, $$$p$$$ is a prime number, $$$2 \le p \lt 10^9$$$). The generator takes time $$$t$$$ as input and outputs $$$(at + b) \mod p$$$.

To demonstrate the unreliability of such a generator, Andrew-13 decided to write a program that, without knowing the numbers $$$a$$$, $$$b$$$, and $$$p$$$, finds them by making queries to the generator. The program is allowed to make no more than $$$13$$$ queries.

Can you write your own program that can solve this task?

Interaction

At the beginning of each test, the numbers $$$a$$$, $$$b$$$, and $$$p$$$ are chosen according to the constraints given.

Then your program begins interaction with the interactor.

To find out the value of the pseudo-random number generator described in the problem, you should output «? $$$t$$$» on a separate line ($$$0 \le t \lt 10^{18}$$$, $$$t$$$ is an integer). You will receive the value $$$(at + b) \mod p$$$.

When your program is ready to provide an answer, it must output «! $$$a$$$ $$$b$$$ $$$p$$$» on a separate line and then terminate.

If you make more than $$$13$$$ queries during the interaction, your program should terminate immediately, and you will receive a Wrong Answer verdict. Otherwise, you may receive any verdict.

After each query output, do not forget to print a newline and flush the output buffer. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
Example
Input

13

4

12
Output
? 6

? 12

? 998244353

! 7 5 17

G. Keyword
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Recently, Moriarty has picked up Sherlock's trail and managed to obtain data about an important event that will occur exactly when a specific high-frequency radio signal transmits the string $$$S$$$.

However, this time Sherlock managed to confuse his main enemy, and he deliberately sent Moriarty this information. Instead of useful data, he will send one of the characters from his encoding alphabet uniformly at random every second. During this time, Moriarty will wait until the substring equal to $$$S$$$ appears in the stream of received characters; after that, he will immediately stop his observations.

Sherlock is very busy right now, so he asked you to determine the expected number of seconds that Moriarty will observe until the string $$$S$$$ appears in the stream. Output the answer modulo $$$998244353$$$.

Input

The first line contains the string $$$A$$$ ($$$1 \le |A| \le 36$$$), consisting of lowercase Latin letters or digits, which represents the set of characters that Sherlock will send uniformly at random. It is guaranteed that all characters in $$$A$$$ are distinct.

The second line contains the string $$$S$$$ ($$$1 \le |S| \le 5 \cdot 10^5$$$), which is the sequence of characters that Moriarty will wait for. It is guaranteed that all characters in $$$S$$$ are among the characters in string $$$A$$$.

Output

In a single line, output the expected number of seconds that Moriarty will wait, modulo $$$998244353$$$.

Examples
Input
01
1
Output
2
Input
abo
aboba
Output
246
Input
andrew13
andrew13
Output
16777216