Description

You are going to maintain a data structure that each element is a person described by a string of name and int of age.

Give you n orders. There're four types of order

born:

The order will followed by a string and a int represented a person's name and age. Insert the new person into the set.

find:

The order will followed by a string and a int. Find out if the person exist in the set or not. If the person exist, print YES, else print NO.

kill

The order will followed by a string and a int. Erase the person from the set.

If you can't find the person, do nothing.

young:

Print the youngest person in the set. If multiple people has the same age, print the person whose name is the smallest lexicographical order.

If you can't find the person, do nothing.

Download the C++ reference.
You will see the file named "12534.cpp" but that's OK.
Just download the file and change the filename extension(副檔名) into "zip" then you can upzip the file and use the reference.
The link is below.

reference.zip

Input

The first line contains only one integer n(1 <= n <= 200000)

The following n lines each lines contains order as the description described.

Each name's length will not exceed 10000.

Each age is in rage of  int

Output

For each order print as demand.

Remember to print \n at the end of each output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

And now my watch begins.

~by a binge watching man

Your a lord commander of the night's watch. You wants to choose some men to be your soldiers while other lords also needs to choose some men. There're n lords and n soldiers and there're k lords who are your friends therefore they will follow your order. And each soldier's ability is represented by a number ai. Since the lords stand in a line and wait for their turn to choose, you are standing in the m-th position.

Given a sequence of numbers a1 ~ an. n people standing in a line to choose one number from the sequence.

Each person can only choose a number from the head or the tail of the sequence.

Once a number is chosen, it will be remove from the sequence.

You are at m-th position of the line.

You want to get the number as big as possible.

You can command at most k people to choose what you want them to choose(head or tail).

But you can not change your command during the choosing process.

And those who you don't give a command will choose arbitrarily.

Your task is to find out what is the greatest integer x such that, no matter what are the choices of the others you didn't choose to control, the element you will take from the array will be at least x?

 

Example:

If there are n=6 numbers 2, 9, 2, 3, 8, 5.

You are at m=4 position.

And you can control k=2 people.

If the first person ordered by you choose tail 5.

The second person ordered by you choose head 2.

Then the third person can choose either 9 or 8.

No matter what the third person choose, you can get at least 8.

Therefore the answer is 8.

Input

The first line of input will be t(1 <= t <= 10) means number of testcases.

Each testcases contains two lines.

First line contains three integers n( 1 <= n <= 5000), m(1 <= m <= n), k(0 <= k <= n-1).

Second line contains n integers ai(1 <= ai <= 10^9).

Output

For each testcases, print a single integer x.

Each output is ended by \n.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Help! Help! We're all gonna be flunked by these devil-like TAs!

── Students

It's said that there's a course that every student who take that course will be flunked...

The course might be Advanced Calculus, Complex Analysis ... it could be Introduction to Programming! Who knows?

The only thing you know is that the professor of this course is Professor Chen-Tzong Hwann(煥陳宗), a.k.a. CTH. His TAs keep producing extremely hard problems, leads that every student are going to be flunked.

However, flunking every student means that CTH needs to submit a report to the administration of the university, and CTH is too lazy to write that report, so he decide to let exactly one student pass.

---

The class have $n$ students, CTH will organize a tournament. The tournament is going to be held with the following format:

1. If there's only one student remaining, then the student is the winner, the tournament ends.

2. If the number of remaining students is even, they split in pairs and compete for each pair. The loser of each pair will be eliminated(no draws for this competition).

3. Otherwise, if the number of remaining students is odd, they'll compete each other once in round robin tournament and decide the final winner, then the tournament ends.

   • For the round robin tournament part, if there are $x$ students remaining, there will be $\frac{x(x-1)}2$ competitions since they compete with everyone once.

For example, if there are 20 students initially, they would have 10 competitions, then 10 students are eliminated. The remaining 10 students would have 5 competitions and remain 5 students, then have 10 competitions for round robin tournament. Totally there are 10+5+10=25 competitions.

CTH's TA want to see exactly $n$ competitions in order to see them suffer. He asks you to calculate the minimum number of students that the course need to have.

---

Hint:

This problem involves brute force(暴力搜尋) and binary search(二分搜尋). One of the solutions is to combine the two techniques. You may try to think what we can enumerate, and what we can do a binary search.

Brute Force: usually applied when the number is small.

Binary Search: If the sequence is in increasing / decreasing order, the binary search technique can be applied.

Input

The first line contains an integer $T$. There are $T$ testcases below. $1\le T\le 64$.

There are $T$ lines below. Each line contains exactly one integer $n$, the number of competitions.

$1\le n\le 10^{18}$.

Output

For each testcase, output its minimum number of students that the course need to have with newline.

If there's no such answer, print -1 instead.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A program a day keep girls away.

~by anonymous programmer

You are a programmer, you need to write code day and night.

In order to keep you in a sharp mind, you drink a lot of coffee.

Given n cups of coffee, the ith cup of coffee has the effect that make

you write ai lines of code and ai will be decreasing order.

Each cup of coffee can only be drunk for once.

You can drink coffee in arbitary order!!!!

You need to write m lines of code.

In a day when you drink a cup of coffee,

the second cup of coffee will loss it's effect by 1

and the third cup of coffee will loss it's effect by 2

..... and so on

You need to find out what's the minimum number of days

that you can finish m lines of code.

 

Example:

Given n = 5 cups of coffee, you need to finish m=16 lines of code.

The effect of coffee = a1 = 5, a2 = 5, a3 = 5, a4 = 5, a5 = 5

If you drink a1~a4 at the first day, you finish 5 + (5-1) + (5-2) + (5-3) = 14 lines of code.

If you drink a5 at the second day, you finish 5 lines of code.

14+5 >= 16 therefore you can finish your code by 2 days,

and it's the minimum number of days that you can achieve.

Input

First line contains one integer t(1 <= t <= 10) which means the number of testcases.

Each testcases contains two lines.

First line contains two integer n(1 <= n <= 2*10^5), m(1 <= m <= 10^9)

Second line contains n numbers ai(1 <= ai <= 10^9)

Output

For each testcase print only one number which means the minimum number of days

that you can finish m lines of code.

If you can't finish your code in any way, print -1.

Remember to print \n at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss