2024 ICPC Universidad Nacional de Colombia Programming Contest
A. Pacman and Russian Roulette
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

To encourage new generations of competitive programmers, the ICPC (Intense Coding Party Committee) is planning new drinking games for the upcoming Shot Contests.

Inspired by old memories of classic Pacman and the Russian Roulette, they wanted to create a new game. One of the ghosts in the original game just moves randomly in the maze. In this new game, both Pacman and the ghost start in the same random position within a 15 square maze without obstacles, but the ghost is hidden until the game ends. Every time the player moves Pacman, the ghost moves to a random adjacent position. After several moves, a button is pressed to reveal the Ghost. If Pacman and the ghost end up in the same position the player lose the game.

While testing the game, they found an issue. Roger, whose debugging skills were second only to his ultimate passion, was called in to find it. After hours of work, Roger identified a problem with the ghost interaction. A programmer had loaded one of the Bomberman's libraries, leaving a bomb that explodes in the starting position after the first move. With each step, the explosion wave expands to all adjacent positions in each one of the four directions. The bomb's expansion wave only affects the ghost. If the ghost lands in the expansion wave, It will remain in that cell until the game ends.

It is important to note that Pacman, the ghost and the expansion wave can go through the border of the maze reaching out the opposite side.

Roger, whose math skills are second only to his debugging skills, tells the committee that the probability of losing the game is really low, but he doesn't have enough time to prove it, he has an ultimate match to play. It is your task to help Roger. For that, you will need to find the probability of losing the game after several moves.

Input

The first line contains a number $$$1 \leq N \leq 50$$$

The second line contains a string S of size N, with the path followed by Pacman; it can contain only the characters 'L', 'R', 'D' , 'U' for the moves left, right, down, and up respectively.

Output

Print the probability of losing the game with a precision of $$$10^{-6}$$$

Examples
Input
1
R
Output
0.250000000
Input
4
RLDU
Output
0.250000000
Input
3
LLR
Output
0.078125000
Note

Pacman, the ghost and the expansion wave can only move in the four directions: left, up, down, right.

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

This is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output) and in Python — sys.stdout.flush().

In this problem, you must assist UNAL's tech team in determining the next unused LDAP given a student's full name. Student names consist of three or four words, with the final two representing the surnames and the preceding word(s) representing the first name(s).

LDAPs are generated sequentially. The initial LDAP is formed by concatenating the first letter of the first given name, the first letter of the second given name (if applicable), the entire first surname, and the first letter of the second surname.

If an LDAP is already taken, the process is repeated by using two letters from the first given name, followed by the first letter of the second given name (if applicable), and the entire first surname. Additional letters from the second surname are then appended until the total number of letters matches the number of letters used from the first given name. This pattern continues, incrementing the number of letters from the first given name by one until all letters from the first given name have been used. Once the first given name is fully used, letters from the second surname can be added as needed until all the second surname is complete.

For example if 'James David Rodriguez Rubiano', had decided to study at UNAL instead of being a football player, his LDAPs progression would have been

  • JDRodriguezR
  • JaDRodriguez
  • JaDRodriguezR
  • JaDRodriguezRu
  • JamDRodriguez
  • JamDRodriguezR
  • JamDRodriguezRu
  • JamDRodriguezRub
  • JameDRodriguez
  • ...
  • JamesDRodriguezRubi
  • JamesDRodriguezRubia
  • JamesDRodriguezRubian
  • JamesDRodriguezRubiano

Another example, for 'alex de hoz' would be:

  • adeh
  • alde
  • aldeh
  • aldeho
  • alede
  • aledeh
  • aledeho
  • aledehoz
  • alexde
  • alexdeh
  • alexdeho
  • alexdehoz

Each of the four names consists of uppercase and lowercase English letters and has a maximum length of 20 characters. It is guaranteed that the combination of the first letter of the second given name and the entire first surname will not appear as a substring within any other name. And also that there is at least one unused LDAP.

You can make queries to the testing system. Each query is a valid LDAP. Flush output stream after printing each query. There are two different responses the testing program can provide:

  • the string "1" (without quotes), if the LDAP in your query has been used;
  • the string "0" (without quotes), if the LDAP in your query has not been used.

When your program guesses the LDAP, print string "! x", where $$$x$$$ is the answer, and terminate your program normally immediately after flushing the output stream.

Your program is allowed to make no more than $$$20$$$ queries (not including printing the answer) to the testing system.

Input

Use standard input to read the responses to the queries.

The first line contains the full name of the student, 3 or 4 words separated by space.

Following lines will contain responses to your queries — strings "0' or "1". The $$$i$$$-th line is a response to your $$$i$$$-th query. When your program will guess the LDAP print "! x", where $$$x$$$ is the answer and terminates your program.

The testing system will allow you to read the response on the query only after your program prints the query for the system and performs flush operation.

Output

To make the queries your program must use standard output.

Your program must print the queries — guessed LDAP $$$x_i$$$, one query per line (do not forget "end of line" after each $$$x_i$$$). After printing each line your program must perform operation flush.

Each of the values $$$x_i$$$ mean the query to the testing system. The response to the query will be given in the input file after you flush output. In case your program guessed the LDAP $$$x$$$, print string "! x", where $$$x$$$ — is the answer, and terminate your program.

Example
Input
james rodriguez rubio
0

0

1
Output
jamrodriguez

jarodriguezr

jrodriguezr

! jarodriguez
Note

LDAPs preserve the capitalization of the names. (If a letter is uppercase in the name should be uppercase in the LDAP, same for lowercase)

This is (possibly) not the actual LDAP creation algorithm. It was designed just for the sake of the problem.

The first part should be a prefix of the first given name, and the last part should be a prefix of the second last name. The last name prefix can only be longer than the first name prefix once the entire first name has been used.

C. s-parkour
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After losing the ICPC (International Collegiate Parkour Contest), you decided to participate in a parkour competition with different rules. You have traveled to Silvestre-land, where a new parkour competition will take place.

Similar to Diomedes-land, in Silvestre-land, there are $$$N$$$ buildings with positive heights $$$h_1, \ldots, h_N$$$, it is guaranteed that all building heights are distinct.

Each round of the competition will face two competitors, and it will take place from building $$$i$$$ to building $$$j$$$, where $$$i \leq j$$$. One competitor will jump between buildings from $$$i$$$ to $$$j$$$, while the other will jump from $$$j$$$ to $$$i$$$.

When a competitor jumps between buildings, they may have to ascend or descend. If the height of the next building is greater than the current one, they must ascend; otherwise, they must descend. For example, if the competitor passes through buildings with heights $$$1, 7, 2$$$, they first ascend and then descend, which we can represent with the sequence UD (Up, Down).

For a competition between buildings $$$(i, j)$$$ to be fair, the number of ascents from $$$i$$$ to $$$j$$$ must be equal to the number of ascents from $$$j$$$ to $$$i$$$. For example, if the buildings between $$$i$$$ and $$$j$$$ have heights $$$1, 7, 2$$$, the competition is fair because, from left to right, the sequence of ascents and descents is UD (one ascent and one descent), and from right to left, it is also UD (one ascent and one descent). However, if the buildings between $$$i$$$ and $$$j$$$ have heights $$$3, 2, 1$$$, the competition would not be fair because the sequence from left to right is DD (no ascents and two descents), but from right to left, it is UU (two ascents and no descents). Finally, if the buildings between $$$i$$$ and $$$j$$$ have heights $$$3, 4, 2, 1, 5$$$, the competition would be fair because the sequence from left to right is UDDU (two ascents and two descents), and from right to left, it is DUUD (two ascents and two descents).

To prepare for the competition, you want to know how many pairs $$$(i, j)$$$ with $$$i \leq j$$$ result in a fair competition.

Input

The input consists of an integer $$$1 \leq N \leq 10^6$$$ representing the number of buildings in Silvestre-land, followed by $$$N$$$ integers representing the heights of the buildings $$$h_1, \ldots, h_N$$$.

$$$1 \leq h_i \leq 10^9$$$ for every $$$i$$$.

Output

Print the number of pairs $$$(i, j)$$$ such that the competition between buildings from $$$i$$$ to $$$j$$$ is a fair competition.

Example
Input
6
6 1 4 9 7 3
Output
10

D. Wise Splitting
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Some time ago, Roger, Cesar, and Andres spent a week exploring Paris. They went to many places together, and did many activities with their friends. In order to use their time as best as they could, when it was time to pay always one person paid for everything and they kept track of all transactions.

That was all fine until it was time to settle up the numbers before going to Egypt. They forgot until the last minute. Their plane is about to board and they have to do this now. They each only have time to send money to one other person in the group. There is no time to lose and they need your help to figure who to send money to. Can you help them?

Input

Input starts with two integers, $$$N$$$ and $$$M$$$ ($$$2 \le N \le 2 * 10^5$$$, $$$ 1 \le M \le 10^6$$$), the number of people in the group and the number of recorded transactions.

The following $$$M$$$ lines each describe a transaction. The $$$i$$$-th line has $$$3$$$ integers $$$A_i$$$, $$$B_i$$$, and $$$C_i$$$ ($$$1 \le A_i$$$, $$$B_i \le N$$$, $$$A_i \ne B_i$$$ , $$$1 \le C_i \le 10^9$$$). This means that person $$$B_i$$$ borrowed $$$C_i$$$ euros from person $$$A_i$$$.

Output

The first line of the input must be an non-negative integer $$$T$$$, the amount of transactions required to settle up.

The next $$$T$$$ lines must contain $$$3$$$ integers $$$A_i$$$, $$$B_i$$$, and $$$C_i$$$ ($$$1 \le A_i$$$, $$$B_i \le N$$$, $$$A_i \ne B_i$$$ , $$$1 \le C_i$$$). This means person $$$A_i$$$ pays person $$$B_i$$$ with $$$C_i$$$ euros in the process of settling up. Note that each person can pay at most once (but may receive money several times).

If there are multiple solutions, you can print any of them.

Examples
Input
2 1
1 2 50
Output
1
2 1 50
Input
3 3
1 2 2
2 3 4
3 1 16
Output
2
1 3 14
3 2 2

E. Chaves and habibi arrays
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Some time ago, Chaves was walking through the Egyptian market, where many vendors offered him products with great discounts. Chaves was captivated by certain arrangements of numbers, called "habibi arrays."

A habibi array of $$$N$$$ elements is an array of distinct numbers where each number is between 1 and $$$10^9$$$. For example, if $$$N = 3$$$, the array $$$[3, 7, 2]$$$ is a habibi array, but the array $$$[3, 3, 2]$$$ is not (because the number 3 is repeated).

Chaves, being an excellent negotiator, offered $0.00001 in cash for one of the habibi arrays. However, the Egyptian vendor indicated that the price of a habibi array must be calculated in a more elaborate way.

To determine the price, we define that an array of $$$N$$$ distinct elements $$$A_1, \ldots, A_N$$$ is melo if we can write the sorted array in ascending order using a stack and $$$2N$$$ operations, where:

In the $$$i$$$-th operation could be of the types:

  1. We add to the stack the first elemento of the array that hasn't been added to the stack, from left to right.
  2. We remove the top element of the stack and write this element in the first empty space of the new array, from left to right.

If at the end of the process, the written numbers are sorted in ascending order and the stack is empty, then the array is melo. For example, the array $$$[3, 2, 1]$$$ is melo because, after three operations of the first kind, the stack becomes $$$[3, 2, 1]$$$ with 1 at the top. We could then remove the top element three times, leaving us with the new array $$$[1, 2, 3]$$$, which is sorted in ascending order.

Other examples:

  • The array $$$[2, 1, 3]$$$ is melo because we can push 2 and 1 onto the stack, then pop 1 and 2 (writing them in order), and finally push and pop 3.
  • The array $$$[1, 2, 3]$$$ is melo because we can push and pop each element in each operation.

A stack is a data structure that operates in a last-in, first-out (LIFO) manner. Elements are added (pushed) to the top and removed (popped) from the top. For example, if we push the elements 1, 2, and 3 onto the stack in that order, the stack will look like this: $$$[1, 2, 3]$$$ (with 3 at the top). If we then pop an element, we will remove 3, and the stack will become $$$[1, 2]$$$.

Finally, the price of a habibi array is the number of melo subarrays it contains. A subarray is a contiguous portion of an array; for example, $$$[1,3]$$$ is a subarray of $$$[1,1,3,2]$$$, but $$$[1,2]$$$ is not.

Given a habibi array, help Chaves determine how much the Egyptian vendor will charge him.

Input

The input consists of an integer $$$1 \leq N \leq 10^6$$$ and a habibi array of $$$N$$$ elements, where each element is distinct and between 1 and $$$10^9$$$.

Output

Print the number of melo subarrays in the given array.

Example
Input
4
2 4 3 1
Output
9
Note

The only subarray that is not melo is $$$[2, 4, 3, 1]$$$ (note that an array is a subarray of itself).

F. Pacman or Shot
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

New generations of competitive programers always hear about the lengendaries Shot Contests, a programming contest mixed with drinking games that left behind a lot stories to tell. During the contest every wrong submission comes with a shot of your favourite booze, every first sumbission allows you to delivery a shot to any team of your choice and every half hour a random team must drink.

Sadly during the last Shot Contest held, the problems were really easy and the drinks so soft. After all the teams solved the problems they wanted to drink more. Jhonny had a brilliant idea, he saw a weird Pacman machine at the corner of the house and told everybody "Whoever that cannot make Pacman escape from the ghost must have to drink".

The machine contains a modified version of the classic Pacman game, where the objective is to escape from the ghost. There is going to be just one ghost in the game that will be always following pacman through the shortest route, he also knows Pacman's route since the beggining. It is important to note that every time Pacman goes trough the border of the maze he is going to jump to the opposite side of the map if that is not a wall. But the Ghost cannot teleport through the borders. If Pacman or the Ghost try to move to a position that contains a wall, they will stay in the current position.

Jhonny wanted to give it a try, given the configuration of the maze and the route followed by Pacman, tell Jhonny if he has to drink or not.

Input

The first line of the input contains elements $$$1 \leq R, C \leq 5*10^3$$$ number of rows and columns of the maze.

Following R lines with C characters, representing the maze, '.' is an empty space , '#' a wall , 'P' pacman position and 'G' ghost position

Finally a string S containing Pacman's path, it can contain only the following characters according the direction 'L' left, 'R', right, 'D' down and 'U', up. $$$|S| \leq 3 * (R+C)$$$

Output

Print 'Yes' or 'No' if the ghost can reach Pacman on time.

Examples
Input
7 7
....P..
..#..#.
..#..#.
..####.
.G.....
.......
.......
RRRRRRDD
Output
Yes
Input
7 7
....P..
..#..#.
..#..#.
..####.
.......
.......
.G.....
RRRRRRDD
Output
No

G. Chocolate Volcano
time limit per test
1 s
memory limit per test
256 megabytes
input
standard input
output
standard output

Jolany is having her birthday again and this time she'll finally get her favorite cake to share with her friends and family: Chocolate Volcano!

A Chocolate Volcano can be represented as a set of $$$n$$$ points on the plane with increasing coordinates over the $$$X$$$-axis, which when connected form the upper hill shape of the Volcano. The first point and the last point are vertically connected to the base of where the cake lays ( corresponding to the $$$Y$$$-axis ).

Since Jolany is planning on hosting $$$m$$$ attendees at her party, she wants to cut her cake into exactly $$$m$$$ pieces of the same area so that each attendee receives the same amount of cake. For this, she'll do $$$m-1$$$ vertical cuts, as this will guarantee that each guest receives a mini Chocolate Volcano on their own.

Can you help Jolany to find where these cutting points must be performed?

Input

The first line of the input contains two integers $$$n,m$$$ ( $$$2$$$ $$$\leq$$$ $$$n,m$$$ $$$\leq$$$ $$$2$$$x$$$10^5$$$ ).

The second line contains $$$n$$$ integers, the $$$i-th$$$ of them corresponding to $$$x_i$$$, which is the $$$x$$$ coordinate of the $$$i-th$$$ point. The third line contains $$$y$$$ coordinates of the $$$n$$$ points in the same format. The coordinates of the points are positive integers up to $$$10^9$$$. For $$$2$$$ $$$\leq$$$ $$$i$$$ $$$\leq$$$ $$$n$$$, it's guaranteed that $$$x_{i-1}$$$ $$$ \lt $$$ $$$x_i$$$.

Output

Print $$$m-1$$$ integers in increasing order representing the $$$x$$$ coordinates of where the cuts must be performed. Your answer will be considered correct if the absolute or relative error is at most $$$10^{-6}$$$.

Examples
Input
5 2
2 5 6 7 10
4 5 4 5 4
Output
6.000000000000
Input
2 3
5 10
5 5
Output
6.666666666667 8.333333333333
Note

Illustration of the first sample; the red line shows where the cut must be performed in order to divide the cake into two equal parts.

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

The Buhos media team is giving emblems to every member of the community that reaches a new rank in Codeforces. In Codeforces, every user has a rank depending on their contest rating. The ranks in Codeforces are:

RankMin RatingMax Rating
$$$\color{gray}{\texttt{newbie}}$$$$$$-\infty$$$1199
$$$\color{green}{\texttt{pupil}}$$$12001399
$$$\color{teal}{\texttt{specialist}}$$$14001599
$$$\color{blue}{\texttt{expert}}$$$16001899
$$$\color{purple}{\texttt{candidate master}}$$$19002099
$$$\color{orange}{\texttt{master}}$$$21002399
$$$\color{red}{\texttt{grandmaster}}$$$2400$$$\infty$$$

Every time a member of the community participates in a contest and gets for the first time to a new rank, they get an emblem from the media team corresponding to the new rank they have achieved. Your task is to help them determine which emblem the member should get according to the results given to you.

Input

In the first line, you get a string $$$S$$$ corresponding to the cf handle of the person ($$$|S| \lt 20$$$, it only includes characters from the English alphabet), an integer $$$C$$$ corresponding to their current rating $$$(-10^9\le C\le 10^9)$$$, an integer $$$M$$$ corresponding to their max rating $$$(0\le M\le 10^9, M\ge C)$$$, and an integer $$$D$$$ corresponding to their delta from the last round $$$(-10^9\le D\le 10^9)$$$.

Output

If they achieved a new rank for the first time, print the rank they achieved. If not, print "Think about it, you can do it!"

Examples
Input
aprohACk 2098 2098 10
Output
master
Input
ahoraSoyPeor 2237 2288 -69
Output
Think about it, you can do it!
Input
demianOneTwoThree 725 725 721
Output
specialist
Input
prins 2092 2275 207
Output
Think about it, you can do it!

I. d-parkour
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

After winning the programming marathon, you decide to seek a new challenge and start training for the ICPC (International Collegiate Parkour Contest). This competition will take place in Diomedes-land.

In Diomedes-land, there are $$$N$$$ buildings with positive heights $$$h_1, \ldots, h_N$$$, and it is guaranteed that all building heights are distinct.

Each round of the competition will face two competitors, and it will take place from building $$$i$$$ to building $$$j$$$, where $$$i \leq j$$$. One competitor will jump between buildings from $$$i$$$ to $$$j$$$, while the other will jump from $$$j$$$ to $$$i$$$.

When a competitor jumps between buildings, they may have to ascend or descend. If the height of the next building is greater than the current one, they must ascend; otherwise, they must descend. For example, if the competitor passes through buildings with heights $$$1, 7, 2$$$, they first ascend and then descend, which we can represent with the sequence UD (Up, Down), note that this sequence could be empty when the competitor pass only one building.

For a competition between buildings $$$(i, j)$$$ to be fair, the sequence of ascents and descents from $$$i$$$ to $$$j$$$ must be the same as from $$$j$$$ to $$$i$$$. For example, if the buildings between $$$i$$$ and $$$j$$$ have heights $$$1, 7, 2$$$, the competition is fair because, from left to right, the sequence of ascents and descents is UD, and from right to left, it is also UD (meaning the competitor going from $$$i$$$ to $$$j$$$ ascends if and only if the competitor going from $$$j$$$ to $$$i$$$ ascends). However, if the buildings between $$$i$$$ and $$$j$$$ have heights $$$3, 2, 1$$$, the competition would not be fair because the sequence from left to right is DD (down twice), but from right to left, it is UU (up twice). Finally, if the buildings between $$$i$$$ and $$$j$$$ have heights $$$3, 4, 2, 1, 5$$$, the competition would not be fair because the sequence from left to right is UDDU, but from right to left, it is DUUD (note that even though they go up and down the same number of times, the sequence of ups and downs is not the same).

To prepare for the competition, you want to know how many pairs $$$(i, j)$$$ with $$$i \leq j$$$ result in a fair competition (you have faith in the ICPC organization).

Input

The input consists of an integer $$$1 \leq N \leq 10^6$$$ representing the number of buildings in Diomedes-land, followed by $$$N$$$ integers representing the heights of the buildings $$$h_1, \ldots, h_N$$$ $$$(1 \leq h_i \leq 10^9$$$ for all $$$1\le i \le N)$$$.

Output

Print the number of pairs $$$(i, j)$$$ such that the competition between buildings from $$$i$$$ to $$$j$$$ is a fair competition.

Example
Input
5
2 5 7 1 3
Output
7

J. Gerrymandering
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ignacio is conspiring to make their candidate win in the next election. He proposed a new method for electing the candidate, and it was accepted by the majority; this was the first step in his conspiracy. Now, you, as an "impartial" observer, have to help him in his next step of the conspiracy! (Or don't help him and see the consequences)

The method is the following: Every voter will sit at a circular table, and then you will divide the voters into $$$K$$$ groups. The members of each of the groups must sit adjacent to each other. After this, each of the groups decides by majority for which candidate they are going to vote; if there is not a majority inside the group, then that group doesn't vote for either candidate. The election would be decided by the candidate that gets the votes from more than half of the groups; if neither candidate achieves this, then another person would choose the partition (and you will see the consequences).

You know the favorite candidate for each of the voters; we have only two candidates (Jota and Leo), and Ignacio wants Jota to win. You have to make the $$$K$$$ groups so that Jota wins the election.

In other words: Given a circular array with two characters ('$$$\texttt{J}$$$' and '$$$\texttt{L}$$$'), you have to partition the array into $$$K$$$ subarrays so that the number of subarrays in which there are more $$$\texttt{J}$$$'s than $$$\texttt{L}$$$'s is greater than $$$\frac{K}{2}$$$.

Input

The first line contains $$$N\; \left(1\le N\le 2\times 10^5\right)$$$ and $$$K$$$ $$$(1\le K \le N$$$) — the number of voters and the number of groups, respectively.

The second line contains $$$N$$$ characters $$$c_1, c_2, \dots, c_n\;$$$ ($$$c_i$$$ is '$$$\texttt{J}$$$' or '$$$\texttt{L}$$$') — the circular array representing the favorite candidate of the $$$i$$$-th voter.

Output

If you can divide the array so that Jota wins, then print 'YES' and in the next line print $$$K$$$ numbers $$$a_1, a_2,\dots, a_k$$$ ($$$1\le a_1 \lt a_2 \lt \cdots \lt a_k\le N$$$) representing the partition of the circular array. The members of the $$$i$$$-th ($$$1\le i \lt k$$$) group would be $$$\{a_i,a_i+1,a_i+2,\dots, a_{i+1}-1\}$$$, and the members of the last group would be $$$\{a_k, a_k+1, \dots,N,1,2,\dots, a_1-1\}$$$.

Otherwise, if you can't divide the array so that Jota wins, print 'NO'.

Examples
Input
5 3
J L J J L
Output
YES
1 4 5
Input
5 3
J L J L L
Output
NO

K. Baby Chaves
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Baby Chaves was playing with his Christmas gift and he got it all messed up, oh no!

His gift was an array of length $$$N$$$ ($$$1\le N\le 10^5$$$) where he can make the following operations: Choose two consecutive numbers in the array, then add $$$k$$$ to one of the numbers and subtract $$$k$$$ from the other one, where $$$k$$$ could be any integer.

Baby Chaves got some of the integers in the array negative, a big mistake as his mom doesn't like negative integers. You don't have much time to fix this before his mom comes home, so tell Baby Chaves what is the minimum number of operations needed to make all the numbers in the array non-negative, that is, greater than or equal to $$$0$$$.

Input

The first line contains $$$N\; (1\le N\le 10^5)$$$ — the length of the array.

The second line contains $$$N$$$ integers $$$a_1, a_2, \dots, a_n\; (-10^9\le a_i \le 10^9)$$$ — the array.

Output

Print $$$-1$$$ if it isn't possible to make all the numbers non-negative; otherwise, print the minimum number of operations needed.

Examples
Input
5
-8 0 15 0 -2
Output
4
Input
5
-10 12 2 -8 2
Output
-1
Input
1
0
Output
0
Note

In the first sample, you could do the following operations:

  • Add $$$8$$$ to the index $$$1$$$ and subtract $$$8$$$ from the index $$$2$$$ to get: $$$[0, -8, 15, 0, -2]$$$.
  • Add $$$8$$$ to the index $$$2$$$ and subtract $$$8$$$ from the index $$$3$$$ to get: $$$[0, 0, 7, 0, -2]$$$.
  • Add $$$2$$$ to the index $$$5$$$ and subtract $$$2$$$ from the index $$$4$$$ to get: $$$[0, 0, 7, -2, 0]$$$.
  • Add $$$2$$$ to the index $$$4$$$ and subtract $$$2$$$ from the index $$$3$$$ to get: $$$[0, 0, 5, 0, 0]$$$.
It can be proven that we need at least $$$4$$$ operations.

In the third sample, the values of the array are already non-negative so you need $$$0$$$ operations.

L. Strobogrammatic
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

An strobogrammatic number is a number that reads the same when displayed upside down, that is, when rotated 180 degrees.

Although some people may find these numbers interesting, the truth is that they're highly dependent on the base and the symbols used when represented. In this occasion we'll be focusing only on numbers represented in a hexadecimal base. For the symbols, we will use the standard symbols used in calculators, these ones:

Your goal is to determine what is the minimum of digits that have to be changed for the number to be strobogrammatic.

Input

You're given a non-negative hexadecimal number of at most $$$10^5$$$ digits consisting only of digits $$$\{0,1,2,3,4,5,6,7,8,9,A,b,C,d,E,F\}$$$.

Output

Output the minimum number of changes you have to make to the number to make it strobogrammatic.

Examples
Input
63181E9
Output
0
Input
4d75b4
Output
5

M. grinch
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Since July, the holiday spirit has been in the air, and as the Grinch you are, you've already set up your Christmas tree. Your Christmas tree can be represented as a tree (in programming terms) with $$$N$$$ nodes and $$$N-1$$$ edges, where there is a unique path between any pair of nodes in the tree.

We define the distance between two nodes in the tree as the number of edges in the unique path between them. Let's call the distance between $$$u$$$ and $$$v$$$ as $$$d(u,v)$$$.

While waiting for midnight on December 25th (only six months to go), you decide to play a game with your friend on the Christmas tree.

The game starts with a token on node $$$u$$$ of the tree. Players alternate turns, with you playing first, then your friend, and so on. On each turn, if the token is on node $$$v$$$ of the tree, the player whose turn it is must move the token to any node $$$w$$$ such that $$$d(v, w) \gt M$$$, where $$$M$$$ is the maximum distance any player has previously moved the token. The player who is unable to make a move loses the game.

For each node $$$u$$$ determine if, starting with the token on node $$$u$$$, you will win the or not, it's known that the players always plays optimally.

Input

The first line of input consists of an integer $$$1 \leq N \leq 10^6$$$ representing the number of nodes in the tree. The next $$$N-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$, representing the edges of the tree.

Output

Print a single line containing a string of $$$0$$$s and $$$1$$$s, where $$$s_i = 1$$$ if and only if starting with the token on node $$$i$$$, you will win the game.

Example
Input
4
1 2
1 3
1 4
Output
0111