2017 PSUT Coding Marathon
A. Smiley Faces (A)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Light got some pieces of paper, each contains one of the three symbols: '.', ':', and ')'.

He wants to use these pieces to form as many smiley faces as possible. To form one smiley face he needs one piece with a bracket ')' on it and either two pieces with dots '.', or one piece with a colon ':'.

Mr. Light has A, B, and C of each symbol of '.', ':', ad ')', respectively. What is the maximum number of smiley faces he can form?

Input

The input contains three space-separated integers A B C (0 ≤ A, B, C ≤ 100), the number of pieces with each symbol of '.', ':', and ')', respectively.

Output

Print the maximum number of smiley faces Mr. Light can form, on a single line.

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

B. Smiley Faces (B)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Light now have a string that consists only of the three characters: ':', '(', and ')'.

Mr. Light considers a colon ‘:’ followed by a closing bracket ')' as a smiley face. So ":)" is a smiley face while "(:" is not. Now he wants to choose exactly one prefix (one or more characters at the beginning) of this string and mirror it (reverse it and flip the brackets).

For example, the string ":):((" mirrored is ")):(:".

What is the maximum number of smiley faces Mr. Light can get in the string after mirroring exactly one prefix?

Input

The input contains a non-empty string of no more than 2 × 105 characters. Each character is either ':', '(', or ')'.

Output

Print the maximum number of smiley faces Mr. Light can get after mirroring exactly one prefix.

Examples
Input
:(:):(:):)
Output
4
Input
:)::(:(:
Output
2

C. Smiley Faces (C)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Light is not satisfied with the number of smiley faces in his string. Now he wants to mirror exactly one substring (one or more consecutive characters in the string) to increase the number of smiley faces as possible. Can you find the maximum number of smiley faces he can achieve?

Input

The input contains a non-empty string of no more than 2 × 105 characters. Each character is either ':', '(', or ')'.

Output

Print the maximum number of smiley faces Mr. Light can achieve by mirroring exactly one substring.

Examples
Input
:(:):(:):)
Output
4
Input
:)::(:(:
Output
3

D. Roads (A)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are N cities numbered from 1 to N with N roads connecting them. The ith road goes between the two cities i and i + 1 (1 ≤ i < N), and the last road goes between the first and the last city. The length of the ith road is wi.

Let dist(u, v) be the length of the shortest path that goes between city u and city v. Your task is to find the total sum of dist(u, v) for all pairs (u, v) (1 ≤ u < v ≤ N).

Input

The first line of input contains a single integer N (3 ≤ N ≤ 2 × 105), the number of cities.

The second line of input contains N space-separated integers wi (1 ≤ wi ≤ 1000), the ith value represents the length of the ith road.

Output

Print the required sum on a single line.

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

E. Roads (B)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Some cities are now occupied. Mr. Light wants to cut all paths that go between specific pairs of cities. Destroying any road on a path cuts that path. The cost of destroying each road di is given.

Mr. Light already destroyed some (one or more) roads, and the cost for the destroyed roads is given as zero. Find the minimum total cost needed to cut all the paths between the given pairs of cities.

Input

The first line of input contains two space-separated integers N, M (3 ≤ N ≤ 2 × 105) , the number of cities and the number of pairs to cut the paths between them, respectively.

The second line of input contains N space-separated integers di (0 ≤ di ≤ 109), the ith value represents the cost of destroying the ith road (or 0 if it is already destroyed).

It is guaranteed that at least one of the roads is already destroyed.

Each of the following M lines contains two space-separated integers u, v (1 ≤ u, v ≤ N) (u ≠ v), representing a pair of cities that should not remain connected. No pair of cities will appear more than once.

Output

Print the minimum cost on a single line.

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

F. Balloons (A)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are N balloons linked together in a line. Each balloon is either red, green, or blue. Mr. Light wants to get exactly one balloon of each color (exactly one red balloon, one green balloon, and one blue balloon) - no more or less. Find the minimum number of cuts he has to make to achieve this.

This picture illustrates the first sample test case: "RRGRGRRB". Each letter represents one of the three colors. After making these cuts, Mr. Light will get the two balloons "GR" and the last balloon "B".

Note that the three balloons Mr. Light will get don't have to be disconnected, and it is only allowed to cut the rope that links the balloons together.

Input

The input contains a string S (3 ≤ |S| ≤ 2 × 105), representing the balloons in the line. Each letter is either 'R', 'G', or 'B' and represents the color of that balloon.

It is guaranteed that for each color, there exists at least one balloon with that color.

Output

Print the minimum number of cuts on a single line.

Examples
Input
RRGRGRRB
Output
3
Input
RGRGBB
Output
2

G. Balloons (B)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Light found that some colors appear more than others, and sometimes, many balloons of the same color are adjacent. He doesn't want to cut the rope and reorder them, instead, he's going to use special light sources.

The color of the balloon changes the first time it is in the range of a light source. Red balloons become blue, green balloons become red, and blue balloons become green.

After the first light source hits it, the color of the balloon never changes again -it will stay in its new color even if another light source hits it. More formally, the color of the balloon changes at most once.

Mr. Light will start turning some lights on, one by one. Each time he wants to know for each color the number of balloons with that color.

Input

The first line of input contains two space-separated integers N, M (1 ≤ N ≤ 2 × 105) , the number of balloons and the number of light sources Mr. Light will turn on.

The second line of input contains a string S of length N, representing the balloons in the line. Each letter is either 'R', 'G', or 'B' and represents the color of that balloon.

Each of the following M lines contains two space-separated integers l, r (1 ≤ l ≤ r ≤ N), representing the range of a light source.

Output

Print M lines, the Kth line contains three integers R G B, each integer is equal to the number of balloons that appear in that color after turning on the first K light sources.

Examples
Input
8 4
RRGRGRRB
1 3
5 8
2 2
2 7
Output
4 1 3
3 1 4
3 1 4
2 1 5
Input
6 3
RGRGBB
1 3
2 4
2 5
Output
1 1 4
2 0 4
2 1 3

H. Data Structures Exam (A)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

It's exam week at PSUT, and Doctor Sufyan is in big trouble; the room he had reserved for his Data Structures exam was preoccupied and the only available room left was the meeting room, which had a single large round table with N seats around it numbered from 1 to N in one direction.

Doctor Sufyan hates cheating, and this particular class of N students was known for cheating in almost every exam they took.

He knows that there are M pairs of friends in this class that are likely to copy each other's answers. However, the two friends will not be able to cheat if there is an even number of students seated between them from both directions.

Given the number of students in this class N, their seating order around the table, and the potential cheating pairs of friends, help Doctor Sufyan figure out the number of pairs that might be able to cheat.

Input

The first line of input contains two space-separated integers N, M (3 ≤ N ≤ 104) , the number of students (and seats) and the number of cheating pairs of friends, respectively.

The second line contains N distinct space-separated integers between 1 and N, representing the seating order of the students around the table; the ith integer represents the ID (from 1 to N) of the student sitting in the ith position.

Each of the following M lines contains two space-separated integers a b (1 ≤ a, b ≤ N) (a ≠ b), represent a pair of friends that are most likely to cheat.

It is guaranteed that each pair of students will appear at most once.

Output

Print the number of pairs of students that might be able to cheat.

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

I. Data Structures Exam (B)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

As predicted, a number of students were able to cheat during the last exam, and Doctor Sufyan wanted to avoid that in the future. He wanted to come up with a specific seating order beforehand that guarantees that no two friends will be able to cheat from each other, in case he had to use the meeting room again.

Given the number of students in his class N, which is equal to the number of seats around the table, and the pairs of friends that are likely to cheat from one another, determine whether or not it's possible to find a seating order that guarantees that no cheating incidents will occur.

Input

The first line of input contains two space-separated integers N, M (3 ≤ N ≤ 104) , the number of students (and seats) and the number of cheating pairs of friends, respectively.

Each of the following M lines contains two space-separated integers a b (1 ≤ a, b ≤ N) (a ≠ b), represent a pair of friends that are most likely to cheat.

It is guaranteed that each pair of students will appear at most once.

Output

If it is impossible to find a seating order that guarantees that no cheating incidents will occur, print -1. Otherwise, print N distinct integers, on a single line, representing the seating order of the students around the table.

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

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

You must have heard of the board game Jackaroo. The lonely geeks of the ACM community at PSUT decided to launch a solo version of that game. Basically, the aim of the game is to try and get all your N marbles to end up in their N home spots (i.e. the green holes at the center of the board as in the picture below).

The lonely geeks decided that this game must be played with an unlimited number of one single lonely card, the 7 card. Using a 7 card, you can move any marble 7 steps, or split the seven moves between two marbles (i.e. the sum of their moves must be 7). The marbles can only move clockwise starting from the outside (i.e. they can't go backwards), no two marbles can be in the same spot after playing any of the cards, and marbles can jump over each other as long as they are not in any of the home spots. The first hole outside the home is numbered 1 and the numbering increases counterclockwise. Given the number of marbles N, and their positions on the board, determine if its possible to get all of your marbles in the homes.

Input

The first line of input contains a single integer N (1 ≤ N ≤ 50), the number of marbles.

The second line of input contains N distinct space-separated integers, each between 1 and 500 and represent the position of one of the marbles.

Output

Print "yes" if it is possible to get all of the marbles in the homes, otherwise print "no".

Examples
Input
3
1 2 8
Output
yes
Input
2
1 4
Output
no
Input
5
1 2 6 7 9
Output
yes