On May 29th, the second qualifying round of the Russian Code Cup 2016 championship was held, which is being held in English for the first time. This time the participants had to solve five problems within two hours. In the second qualifying round, 3891 people fought, and the top 200 won the right to participate in the qualifying round, which will be held on June 19. And today we offer you to familiarize yourself with the solutions of the proposed tasks.

1. Peter and textbook
2. Gregory and the Bank
3. Name generators
4. T-shirts
5. Bridge testing

Task A. Peter and the textbook

Condition
')
Time limit of 2 seconds
256 MB memory limit

Cleaning up the room today, Petya found his old Russian textbook. Since he had disliked the subject since childhood, he began to tear pages from it.

In the textbook, n pages, numbered from 1 to n , which are bound by a binding so that i and n - i + 1 pages are connected to each other — if you pull out one of them, the second one also drops out of the textbook. Petyu really likes the process of tearing pages from the textbook, but he still wants to control it, and it is interesting at some points in time that he is interested in knowing what number the p- th page has in order of the rest. Help him with this task.

Input Format

The input contains several test cases. The first line contains the number of tests t (1 ≤ t ≤ 1000).

Each of the following t tests is described as follows: the first line of the test description contains two numbers n , q (2 ≤ n ≤ 100, n is even, 1 ≤ q ≤ 100) - the number of pages in the textbook and the number of queries, respectively. The following q lines contain two types of queries:

• - i - Peter tears out the page with the number i ;
• ? p - Petya wants to find out which number is in the p- th of the remaining pages.

It is guaranteed that in the request of the first type the page to be deleted exists, and in the request of the second type the current number of pages is not less than p .

Output format

For each request of the second type in a separate line print the number of the page you are looking for.

Examples

Input data
2
4 4
? 3
- 2
? 2
? one
6 5
- 3
? 3
- one
? 2
? one

Output
3
four
one
five
five
2

Decision

In this task, you just had to write what was asked. It is enough to store an array of isDeleted of size n , where isDeleted [i] means whether page i has already been torn out. To process the first request, it is sufficient to set isDeleted [i] and isDeleted [ n - i + 1] to false, and to process the second request, find the index of the pth true in the isDeleted array.

Asymptotic solution: O (t • q • n) .

Problem V. Gregory and the Bank

Condition

Time limit of 2 seconds
256 MB memory limit

Gregory works in accounting at one large enterprise. He receives bank transfers from buyers and transfers money to sellers.

Grigory receives and sends all transfers through the only available branch of the bank where his company is serviced. The work of this department is rather strange. Every day, the bank works in one of two ways: it allows customers to either send or only accept money transfers. At the same time, Gregory can perform at most one operation: receive one transfer or make one transfer, depending on the type of operation allowed on that day. Counterparty, you can choose at your discretion. In this case, the head of St. Gregory makes him necessarily go to the bank and send or receive transfers every day, otherwise he decides that Gregory does not work, and will dismiss him.

Gregory must process n requests for receiving money from buyers and m requests for sending money to sellers. Gregory knows the schedule of the bank, and can also agree with each buyer and seller about when the money will be transferred.

At the initial moment on the account, which is managed by Gregory, there is no money. Then he comes to the bank every day and either receives money into the account or sends it from him. At the same time, he understands that it may turn out that he will not be able to pay off some sellers. Gregory will not be able to pay if, upon the arrival of the agreed payment date, he has less money in his account than is required to pay the seller’s services. In this case, the money is not transferred from the account, and Gregory is reprimanded from his superiors. Offended seller refuses to deliver the goods and no longer interacts with the firm of Gregory.

Gregory wants to negotiate days of settlement with sellers and buyers so that sellers with whom he cannot pay will be as small as possible. Help him do it!

Input Format

The input contains several test cases. The first line contains the number of tests t (1 ≤ t ≤ 1000).

Each of the tests is described as follows: the first line of the test description contains the numbers n and m (1 ≤ n , m ≤ 100) - the number of buyers and sellers, respectively. The second line contains n numbers a _i (1 ≤ a _i ≤ 1000) - the amount to be transferred by the i -th customer. The third line contains m numbers b _j (1 ≤ b _j ≤ 1000) - the amount to be transferred to the jth seller. The last line of the test description contains the string s (the length s is equal to n + m , s contains n characters + and m characters -). s [k] equals +, if on k- th day the bank allows only accepting money transfers, and if the bank works only for sending transfers, then s [k] is equal to -.

Output format

For each test in a separate line print the answer to it - the minimum possible number of sellers with whom Gregory can not pay.

Examples

Input data
3
2 1
15
four
+ - +
13
one
2 2 2
- + -
2 2
2 2
3 3
+ - + -

Output
0
3
one

Decision

The idea of ​​solving this problem is based on greedy algorithms. Consider the random arrangement of buyers and sellers.

Suppose we have a pair of buyers a _i and a _j , i < j and a _i < a _j . i and j are the positions in the selected random arrangement. If you swap them, it is obvious that the answer will not worsen, since the amount of money in the account of Gregory will increase in the segment from i to j . Therefore, it is advantageous for buyers to transfer money in descending order of a _i .

Similarly, you can prove that if there are two vendors with whom you can pay, it is more profitable to put them in ascending order b _j .

The only subtle point - is the presence of sellers who can not pay. Obviously, if Gregory cannot pay x sellers, then it is more profitable that they are the most expensive.

Based on the above, we obtain a solution to the problem. We sort the sequences a _i and b _j , after which we simulate the process, maintaining the current balance of Gregory.

Task C. Name Generators

Condition

Time limit of 2 seconds
256 MB memory limit

The greatest writer of all times, Henk Morbuks, has already thought of what the next bestseller will write about, but has not yet decided on the names of his characters. As for previous books, he will receive names by dividing a specially invented line into k different and non-empty parts. Help Henk see if it’s possible to split a given string into k different names.

Input Format

The first line of the file contains the number of tests t (1 ≤ t ≤ 1000).

Each test is described in two lines. The first line of the test description contains a string of length not more than 100, consisting of lowercase English letters. The second line contains one positive number k (1 ≤ k ≤ 5) - into which number of different lines the given number should be divided.

Output format

The result of each test should be displayed in the format described below.

If you can split the source line in the described way, the output file should contain k + 1 lines. The first line should contain YES. ( i + 1) -th line must contain the i -th name. The source string must be a concatenation of strings in the order of output.

If you can not split the source line in the manner described, the output file should contain one line NO.

Examples

Input data
3
aaa
2
aaa
3
abc
3

Output
YES
a
aa
NO
YES
a
b
c

Decision

First of all, we note that for any k all lines with a length greater than or equal to k ( k + 1) / 2 can be divided into k different ones. To do this, we take substrings of length 1, 2, ..., k - 1 and n - k ( k - 1) / 2. Since k ≤ 5, we learned how to break all the lines with a length of at least 15. And for lines of length less than 15 we run a search on all k - 1 positions in which we break it, and check if it’s true that in the resulting partition all lines various.

Problem D. T-shirts

Condition

Time limit of 2 seconds
256 MB memory limit

Ilya, Vanya and Vlad have long been participating in team programming competitions. This year n team competitions were held, in each of which the guys got a T-shirt. We assume that the types of T-shirts are numbered from 1 to n , in accordance with the competitions at which they were awarded.

Every boy has a favorite T-shirt, a little less favorite, and so on. Namely, each boy has a permutation of numbers from 1 to n - the numbers of T-shirts, the first of which is the most favorite, and the last - the most disliked.

Now the guys in the competition. They want to wear the same T-shirts for every contest. But their preferences for T-shirts may differ, so before the contest they wrote down numbers from 1 to n and, in turn, crossed out one number at a time. The guys wear the t-shirt, the number of which will be the last one this time.

The guys always cross out optimally, that is, everyone tries to make sure that the T-shirt that he likes the most is left in the end. Therefore, the guys decided to ask you to write a program that will find the number of the T-shirt, which will remain in the end.

Input Format

The input contains several test cases. The first line contains one number t (1 ≤ t ≤ 50) - the number of tests. The following are descriptions of tests.

Each test is defined as follows: the first line contains one positive integer n (1 ≤ n ≤ 13) - the number of competitions in which the guys participated.

The next line contains a permutation from 1 to n - preferences of Ilya's T-shirts.

The next line contains the permutation from 1 to n - preferences of Vani’s T-shirts.

The next line contains the permutation from 1 to n - preferences of Vlad's T-shirts.

The guys go in the following order: Ilya, Vanya, Vlad.

Output format

For each test case, print a single number - the number of the T-shirt, which will remain in the end.

Examples

Input data
3
four
1 3 2 4
4 1 2 3
1 2 3 4
five
1 3 2 4 5
5 3 2 1 4
1 3 2 4 5
3
1 2 3
1 2 3
1 2 3

Output
one
3
one

Decision

To solve this problem, we use dynamic programming on subsets. Let us denote as dp [i] [mask] the optimal T-shirt number that the i- th participant can achieve if he makes a move and he has T-shirts available that correspond to the set bits in the mask number. To recalculate, let's sort out what shirt he will cross out, and find out what shirt he will get using the value dp [( i + 1)% 3] [ mask 1], where mask 1 is obtained from mask by zeroing the corresponding bit.

Problem E. Testing bridges

Condition

Time limit 4 seconds
256 MB memory limit

A small state located on the islands is developing its transport system. Some of the islands are connected by bridges in such a way that between any two islands there is a single path through the bridges, in other words, the system of bridges forms a tree. Bridges can have different lengths.

Before opening these bridges for all, you need to check their reliability. For this, for q days, two workers will travel at a fixed speed 1 along a certain path from one island to another. Each of them will travel along its own path, possibly starting at different points in time. The bridge is considered to be tested on the i- th day if both workers were driving on it at the same time for a non-zero time period at the same time. For each of the q days of testing, determine if at least one bridge was tested on that day.

Input Format

The first line contains two numbers n and q (1 ≤ n , q ≤ 10 ⁵ , n ≥ 2) - the number of islands and days of testing, respectively. The next n - 1 lines describe bridges in the format u _i v _i l _i (1 ≤ u _i , v _i ≤ n , 1 ≤ l _i ≤ 10 ⁹ ) - the ends of the bridge and its length. Each of the following q lines contains descriptions of the two working paths. Each path is given by three numbers b _i , e _i , s _i (1 b _{i i} , e _i ≤ n , 1 ≤ s _i ≤ 10 ⁹ , b _i e _i ) is the starting and ending vertex of the path, as well as the time which worker will start moving.

Output format

Print q lines of answers to the queries. In the i- th line output YES if at least one bridge was tested on the i- th day, and NO otherwise.

Examples

Input data
8 6
1 2 3
1 3 1
1 4 2
2 5 5
2 6 1
5 7 2
5 8 4
5 3 2 7 4 2
8 6 1 1 7 6
4 5 1 4 5 10
7 8 3 3 4 5
6 7 6 5 1 2
2 1 10 8 3 3

Output
YES
YES
NO
NO
NO
YES

Decision

We will solve all requests independently of each other, online. First we find the intersection of two paths and from each of the paths we leave only this intersection.

How to find the intersection of two paths? To do this, we “project” each of the ends of the second path onto the first path. The projection of the vertex u onto the path s → t is the vertex lying on the path s → t , which is closest to u by distance in the tree. This vertex can be one of the following vertices:

• s or t ;
• LCA ( s , t );
• LCA ( s , u ), if it lies on the path s → t ;
• LCA ( t , u ) if it lies on the path s → t .

The path between the projections of each of the vertices of the second path onto the first one will be the desired intersection; we denote it by s ' → t' .

After that, two cases should be considered:

• The paths go along this intersection in different directions. In this case, you can find a moment in time when both workers will be at the same point (do not forget that it can be a half-integer). After that, it remains to verify that this moment in time corresponds to an edge, and not a vertex.
• The paths go in one direction. In this case, it can be shown that if both workers at one point in time were on the same edge, then this is also true for the edge with the maximum length on the path s ' → t' . If the maximum edge length on s ' → t' is equal to M , then the answer is YES if and only if | t ₁ - t ₂ | < M , where t ₁ and t ₂ is the start time.

The solution described above used the LCA search, the search for the maximum edge in the path and the distance between two vertices. All this can be implemented, for example, using the binary ascents technique in O (( n + q ) log n ) time and O ( n log n ) memory.

***
The Russian Code Cup Championship is one of the Mail.Ru Group initiatives aimed at the development of the Russian IT industry and integrated with the IT.Mail.Ru resource. The IT.Mail.Ru platform is designed for those who are keen on IT and are seeking to develop professionally in this area. The project combines the championships of the Russian Ai Cup, the Russian Code Cup and the Russian Developers Cup, educational projects Technopark in MSTU. Bauman, Technosphere at Moscow State University. Mv Lomonosov and Tehnotrek MIPT. In addition, using IT.Mail.Ru, you can use tests to test your knowledge of popular programming languages, learn important news from the IT world, visit or watch broadcasts from specialized events and lectures on IT topics.