Мисис 2023 осень - массивы, строки
A. Oath of the Night's Watch
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

"Night gathers, and now my watch begins. It shall not end until my death. I shall take no wife, hold no lands, father no children. I shall wear no crowns and win no glory. I shall live and die at my post. I am the sword in the darkness. I am the watcher on the walls. I am the shield that guards the realms of men. I pledge my life and honor to the Night's Watch, for this night and all the nights to come." — The Night's Watch oath.

With that begins the watch of Jon Snow. He is assigned the task to support the stewards.

This time he has n stewards with him whom he has to provide support. Each steward has his own strength. Jon Snow likes to support a steward only if there exists at least one steward who has strength strictly less than him and at least one steward who has strength strictly greater than him.

Can you find how many stewards will Jon support?

Input

First line consists of a single integer n (1 ≤ n ≤ 105) — the number of stewards with Jon Snow.

Second line consists of n space separated integers a1, a2, ..., an (0 ≤ ai ≤ 109) representing the values assigned to the stewards.

Output

Output a single integer representing the number of stewards which Jon will feed.

Examples
Input
2
1 5
Output
0
Input
3
1 2 5
Output
1
Note

In the first sample, Jon Snow cannot support steward with strength 1 because there is no steward with strength less than 1 and he cannot support steward with strength 5 because there is no steward with strength greater than 5.

In the second sample, Jon Snow can support steward with strength 2 because there are stewards with strength less than 2 and greater than 2.

B. Vlad and Cafes
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Vlad likes to eat in cafes very much. During his life, he has visited cafes n times. Unfortunately, Vlad started to feel that his last visits are not any different from each other. To fix that Vlad had a small research.

First of all, Vlad assigned individual indices to all cafes. Then, he wrote down indices of cafes he visited in a row, in order of visiting them. Now, Vlad wants to find such a cafe that his last visit to that cafe was before his last visits to every other cafe. In other words, he wants to find such a cafe that he hasn't been there for as long as possible. Help Vlad to find that cafe.

Input

In first line there is one integer n (1 ≤ n ≤ 2·105) — number of cafes indices written by Vlad.

In second line, n numbers a1, a2, ..., an (0 ≤ ai ≤ 2·105) are written — indices of cafes in order of being visited by Vlad. Vlad could visit some cafes more than once. Note that in numeration, some indices could be omitted.

Output

Print one integer — index of the cafe that Vlad hasn't visited for as long as possible.

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

In first test, there are three cafes, and the last visits to cafes with indices 1 and 2 were after the last visit to cafe with index 3; so this cafe is the answer.

In second test case, there are also three cafes, but with indices 1, 2 and 4. Cafes with indices 1 and 4 were visited after the last visit of cafe with index 2, so the answer is 2. Note that Vlad could omit some numbers while numerating the cafes.

C. The Rank
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

John Smith knows that his son, Thomas Smith, is among the best students in his class and even in his school. After the students of the school took the exams in English, German, Math, and History, a table of results was formed.

There are $$$n$$$ students, each of them has a unique id (from $$$1$$$ to $$$n$$$). Thomas's id is $$$1$$$. Every student has four scores correspond to his or her English, German, Math, and History scores. The students are given in order of increasing of their ids.

In the table, the students will be sorted by decreasing the sum of their scores. So, a student with the largest sum will get the first place. If two or more students have the same sum, these students will be sorted by increasing their ids.

Please help John find out the rank of his son.

Input

The first line contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of students.

Each of the next $$$n$$$ lines contains four integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$, and $$$d_i$$$ ($$$0\leq a_i, b_i, c_i, d_i\leq 100$$$) — the grades of the $$$i$$$-th student on English, German, Math, and History. The id of the $$$i$$$-th student is equal to $$$i$$$.

Output

Print the rank of Thomas Smith. Thomas's id is $$$1$$$.

Examples
Input
5
100 98 100 100
100 100 100 100
100 100 99 99
90 99 90 100
100 98 60 99
Output
2
Input
6
100 80 90 99
60 60 60 60
90 60 100 60
60 100 60 80
100 100 0 100
0 0 0 0
Output
1
Note

In the first sample, the students got total scores: $$$398$$$, $$$400$$$, $$$398$$$, $$$379$$$, and $$$357$$$. Among the $$$5$$$ students, Thomas and the third student have the second highest score, but Thomas has a smaller id, so his rank is $$$2$$$.

In the second sample, the students got total scores: $$$369$$$, $$$240$$$, $$$310$$$, $$$300$$$, $$$300$$$, and $$$0$$$. Among the $$$6$$$ students, Thomas got the highest score, so his rank is $$$1$$$.

D. Watering System
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Arkady wants to water his only flower. Unfortunately, he has a very poor watering system that was designed for $$$n$$$ flowers and so it looks like a pipe with $$$n$$$ holes. Arkady can only use the water that flows from the first hole.

Arkady can block some of the holes, and then pour $$$A$$$ liters of water into the pipe. After that, the water will flow out from the non-blocked holes proportionally to their sizes $$$s_1, s_2, \ldots, s_n$$$. In other words, if the sum of sizes of non-blocked holes is $$$S$$$, and the $$$i$$$-th hole is not blocked, $$$\frac{s_i \cdot A}{S}$$$ liters of water will flow out of it.

What is the minimum number of holes Arkady should block to make at least $$$B$$$ liters of water flow out of the first hole?

Input

The first line contains three integers $$$n$$$, $$$A$$$, $$$B$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le B \le A \le 10^4$$$) — the number of holes, the volume of water Arkady will pour into the system, and the volume he wants to get out of the first hole.

The second line contains $$$n$$$ integers $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le 10^4$$$) — the sizes of the holes.

Output

Print a single integer — the number of holes Arkady should block.

Examples
Input
4 10 3
2 2 2 2
Output
1
Input
4 80 20
3 2 1 4
Output
0
Input
5 10 10
1000 1 1 1 1
Output
4
Note

In the first example Arkady should block at least one hole. After that, $$$\frac{10 \cdot 2}{6} \approx 3.333$$$ liters of water will flow out of the first hole, and that suits Arkady.

In the second example even without blocking any hole, $$$\frac{80 \cdot 3}{10} = 24$$$ liters will flow out of the first hole, that is not less than $$$20$$$.

In the third example Arkady has to block all holes except the first to make all water flow out of the first hole.

E. YES or YES?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a string $$$s$$$ of length $$$3$$$, consisting of uppercase and lowercase English letters. Check if it is equal to "YES" (without quotes), where each letter can be in any case. For example, "yES", "Yes", "yes" are all allowable.

Input

The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — the number of testcases.

The description of each test consists of one line containing one string $$$s$$$ consisting of three characters. Each character of $$$s$$$ is either an uppercase or lowercase English letter.

Output

For each test case, output "YES" (without quotes) if $$$s$$$ satisfies the condition, and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).

Example
Input
10
YES
yES
yes
Yes
YeS
Noo
orZ
yEz
Yas
XES
Output
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
Note

The first five test cases contain the strings "YES", "yES", "yes", "Yes", "YeS". All of these are equal to "YES", where each character is either uppercase or lowercase.

F. Mammoth's Genome Decoding
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The process of mammoth's genome decoding in Berland comes to its end!

One of the few remaining tasks is to restore unrecognized nucleotides in a found chain s. Each nucleotide is coded with a capital letter of English alphabet: 'A', 'C', 'G' or 'T'. Unrecognized nucleotides are coded by a question mark '?'. Thus, s is a string consisting of letters 'A', 'C', 'G', 'T' and characters '?'.

It is known that the number of nucleotides of each of the four types in the decoded genome of mammoth in Berland should be equal.

Your task is to decode the genome and replace each unrecognized nucleotide with one of the four types so that the number of nucleotides of each of the four types becomes equal.

Input

The first line contains the integer n (4 ≤ n ≤ 255) — the length of the genome.

The second line contains the string s of length n — the coded genome. It consists of characters 'A', 'C', 'G', 'T' and '?'.

Output

If it is possible to decode the genome, print it. If there are multiple answer, print any of them. If it is not possible, print three equals signs in a row: "===" (without quotes).

Examples
Input
8
AG?C??CT
Output
AGACGTCT
Input
4
AGCT
Output
AGCT
Input
6
????G?
Output
===
Input
4
AA??
Output
===
Note

In the first example you can replace the first question mark with the letter 'A', the second question mark with the letter 'G', the third question mark with the letter 'T', then each nucleotide in the genome would be presented twice.

In the second example the genome is already decoded correctly and each nucleotide is exactly once in it.

In the third and the fourth examples it is impossible to decode the genom.

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

A word or a sentence in some language is called a pangram if all the characters of the alphabet of this language appear in it at least once. Pangrams are often used to demonstrate fonts in printing or test the output devices.

You are given a string consisting of lowercase and uppercase Latin letters. Check whether this string is a pangram. We say that the string contains a letter of the Latin alphabet if this letter occurs in the string in uppercase or lowercase.

Input

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of characters in the string.

The second line contains the string. The string consists only of uppercase and lowercase Latin letters.

Output

Output "YES", if the string is a pangram and "NO" otherwise.

Examples
Input
12
toosmallword
Output
NO
Input
35
TheQuickBrownFoxJumpsOverTheLazyDog
Output
YES
H. Hotelier
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Amugae has a hotel consisting of $$$10$$$ rooms. The rooms are numbered from $$$0$$$ to $$$9$$$ from left to right.

The hotel has two entrances — one from the left end, and another from the right end. When a customer arrives to the hotel through the left entrance, they are assigned to an empty room closest to the left entrance. Similarly, when a customer arrives at the hotel through the right entrance, they are assigned to an empty room closest to the right entrance.

One day, Amugae lost the room assignment list. Thankfully Amugae's memory is perfect, and he remembers all of the customers: when a customer arrived, from which entrance, and when they left the hotel. Initially the hotel was empty. Write a program that recovers the room assignment list from Amugae's memory.

Input

The first line consists of an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of events in Amugae's memory.

The second line consists of a string of length $$$n$$$ describing the events in chronological order. Each character represents:

  • 'L': A customer arrives from the left entrance.
  • 'R': A customer arrives from the right entrance.
  • '0', '1', ..., '9': The customer in room $$$x$$$ ($$$0$$$, $$$1$$$, ..., $$$9$$$ respectively) leaves.

It is guaranteed that there is at least one empty room when a customer arrives, and there is a customer in the room $$$x$$$ when $$$x$$$ ($$$0$$$, $$$1$$$, ..., $$$9$$$) is given. Also, all the rooms are initially empty.

Output

In the only line, output the hotel room's assignment status, from room $$$0$$$ to room $$$9$$$. Represent an empty room as '0', and an occupied room as '1', without spaces.

Examples
Input
8
LLRL1RL1
Output
1010000011
Input
9
L0L0LLRR9
Output
1100000010
Note

In the first example, hotel room's assignment status after each action is as follows.

  • First of all, all rooms are empty. Assignment status is 0000000000.
  • L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000.
  • L: one more customer from the left entrance. Assignment status is 1100000000.
  • R: one more customer from the right entrance. Assignment status is 1100000001.
  • L: one more customer from the left entrance. Assignment status is 1110000001.
  • 1: the customer in room $$$1$$$ leaves. Assignment status is 1010000001.
  • R: one more customer from the right entrance. Assignment status is 1010000011.
  • L: one more customer from the left entrance. Assignment status is 1110000011.
  • 1: the customer in room $$$1$$$ leaves. Assignment status is 1010000011.

So after all, hotel room's final assignment status is 1010000011.

In the second example, hotel room's assignment status after each action is as follows.

  • L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000.
  • 0: the customer in room $$$0$$$ leaves. Assignment status is 0000000000.
  • L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000 again.
  • 0: the customer in room $$$0$$$ leaves. Assignment status is 0000000000.
  • L: a customer arrives to the hotel through the left entrance. Assignment status is 1000000000.
  • L: one more customer from the left entrance. Assignment status is 1100000000.
  • R: one more customer from the right entrance. Assignment status is 1100000001.
  • R: one more customer from the right entrance. Assignment status is 1100000011.
  • 9: the customer in room $$$9$$$ leaves. Assignment status is 1100000010.

So after all, hotel room's final assignment status is 1100000010.