meetforever/GRPO_CL huggingface dataset:
user: Alice got tired of playing the tag game by the usual rules so she offered Bob a little modification to it. Now the game should be played on an undirected rooted tree of n vertices. Vertex 1 is the root of the tree.

Alice starts at vertex 1 and Bob starts at vertex x (x ≠ 1). The moves are made in turns, Bob goes first. In one move one can either stay at the current vertex or travel to the neighbouring one.

The game ends when Alice goes to the same vertex where Bob is standing. Alice wants to minimize the total number of moves and Bob wants to maximize it.

You should write a program which will determine how many moves will the game last.


-----Input-----

The first line contains two integer numbers n and x (2 ≤ n ≤ 2·10^5, 2 ≤ x ≤ n).

Each of the next n - 1 lines contains two integer numbers a and b (1 ≤ a, b ≤ n) — edges of the tree. It is guaranteed that the edges form a valid tree.


-----Output-----

Print the total number of moves Alice and Bob will make.


-----Examples-----
Input
4 3
1 2
2 3
2 4

Output
4

Input
5 2
1 2
2 3
3 4
2 5

Output
6



-----Note-----

In the first example the tree looks like this:

 [Image] 

The red vertex is Alice's starting position, the blue one is Bob's. Bob will make the game run the longest by standing at the vertex 3 during all the game. So here are the moves:

B: stay at vertex 3

A: go to vertex 2

B: stay at vertex 3

A: go to vertex 3

In the second example the tree looks like this:

 [Image] 

The moves in the optimal strategy are:

B: go to vertex 3

A: go to vertex 2

B: go to vertex 4

A: go to vertex 3

B: stay at vertex 4

A: go to vertex 4
user: You're given an array $a$. You should repeat the following operation $k$ times: find the minimum non-zero element in the array, print it, and then subtract it from all the non-zero elements of the array. If all the elements are 0s, just print 0.


-----Input-----

The first line contains integers $n$ and $k$ $(1 \le n,k \le 10^5)$, the length of the array and the number of operations you should perform.

The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 10^9)$, the elements of the array.


-----Output-----

Print the minimum non-zero element before each operation in a new line.


-----Examples-----
Input
3 5
1 2 3

Output
1
1
1
0
0

Input
4 2
10 3 5 3

Output
3
2



-----Note-----

In the first sample:

In the first step: the array is $[1,2,3]$, so the minimum non-zero element is 1.

In the second step: the array is $[0,1,2]$, so the minimum non-zero element is 1.

In the third step: the array is $[0,0,1]$, so the minimum non-zero element is 1.

In the fourth and fifth step: the array is $[0,0,0]$, so we printed 0.

In the second sample:

In the first step: the array is $[10,3,5,3]$, so the minimum non-zero element is 3.

In the second step: the array is $[7,0,2,0]$, so the minimum non-zero element is 2.
user: Ivan has n different boxes. The first of them contains some balls of n different colors.

Ivan wants to play a strange game. He wants to distribute the balls into boxes in such a way that for every i (1 ≤ i ≤ n) i-th box will contain all balls with color i.

In order to do this, Ivan will make some turns. Each turn he does the following:  Ivan chooses any non-empty box and takes all balls from this box;  Then Ivan chooses any k empty boxes (the box from the first step becomes empty, and Ivan is allowed to choose it), separates the balls he took on the previous step into k non-empty groups and puts each group into one of the boxes. He should put each group into a separate box. He can choose either k = 2 or k = 3. 

The penalty of the turn is the number of balls Ivan takes from the box during the first step of the turn. And penalty of the game is the total penalty of turns made by Ivan until he distributes all balls to corresponding boxes.

Help Ivan to determine the minimum possible penalty of the game!


-----Input-----

The first line contains one integer number n (1 ≤ n ≤ 200000) — the number of boxes and colors.

The second line contains n integer numbers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where a_{i} is the number of balls with color i.


-----Output-----

Print one number — the minimum possible penalty of the game.


-----Examples-----
Input
3
1 2 3

Output
6

Input
4
2 3 4 5

Output
19



-----Note-----

In the first example you take all the balls from the first box, choose k = 3 and sort all colors to corresponding boxes. Penalty is 6.

In the second example you make two turns:   Take all the balls from the first box, choose k = 3, put balls of color 3 to the third box, of color 4 — to the fourth box and the rest put back into the first box. Penalty is 14;  Take all the balls from the first box, choose k = 2, put balls of color 1 to the first box, of color 2 — to the second box. Penalty is 5. 

Total penalty is 19.
user: Tenten runs a weapon shop for ninjas. Today she is willing to sell $n$ shurikens which cost $1$, $2$, ..., $n$ ryo (local currency). During a day, Tenten will place the shurikens onto the showcase, which is empty at the beginning of the day. Her job is fairly simple: sometimes Tenten places another shuriken (from the available shurikens) on the showcase, and sometimes a ninja comes in and buys a shuriken from the showcase. Since ninjas are thrifty, they always buy the cheapest shuriken from the showcase.

Tenten keeps a record for all events, and she ends up with a list of the following types of records:

  + means that she placed another shuriken on the showcase;  - x means that the shuriken of price $x$ was bought. 

Today was a lucky day, and all shurikens were bought. Now Tenten wonders if her list is consistent, and what could be a possible order of placing the shurikens on the showcase. Help her to find this out!


-----Input-----

The first line contains the only integer $n$ ($1\leq n\leq 10^5$) standing for the number of shurikens. 

The following $2n$ lines describe the events in the format described above. It's guaranteed that there are exactly $n$ events of the first type, and each price from $1$ to $n$ occurs exactly once in the events of the second type.


-----Output-----

If the list is consistent, print "YES". Otherwise (that is, if the list is contradictory and there is no valid order of shurikens placement), print "NO".

In the first case the second line must contain $n$ space-separated integers denoting the prices of shurikens in order they were placed. If there are multiple answers, print any.


-----Examples-----
Input
4
+
+
- 2
+
- 3
+
- 1
- 4

Output
YES
4 2 3 1 

Input
1
- 1
+

Output
NO

Input
3
+
+
+
- 2
- 1
- 3

Output
NO



-----Note-----

In the first example Tenten first placed shurikens with prices $4$ and $2$. After this a customer came in and bought the cheapest shuriken which costed $2$. Next, Tenten added a shuriken with price $3$ on the showcase to the already placed $4$-ryo. Then a new customer bought this $3$-ryo shuriken. After this she added a $1$-ryo shuriken. Finally, the last two customers bought shurikens $1$ and $4$, respectively. Note that the order $[2, 4, 3, 1]$ is also valid.

In the second example the first customer bought a shuriken before anything was placed, which is clearly impossible.

In the third example Tenten put all her shurikens onto the showcase, after which a customer came in and bought a shuriken with price $2$. This is impossible since the shuriken was not the cheapest, we know that the $1$-ryo shuriken was also there.
user: Little girl Susie went shopping with her mom and she wondered how to improve service quality. 

There are n people in the queue. For each person we know time t_{i} needed to serve him. A person will be disappointed if the time he waits is more than the time needed to serve him. The time a person waits is the total time when all the people who stand in the queue in front of him are served. Susie thought that if we swap some people in the queue, then we can decrease the number of people who are disappointed. 

Help Susie find out what is the maximum number of not disappointed people can be achieved by swapping people in the queue.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5).

The next line contains n integers t_{i} (1 ≤ t_{i} ≤ 10^9), separated by spaces.


-----Output-----

Print a single number — the maximum number of not disappointed people in the queue.


-----Examples-----
Input
5
15 2 1 5 3

Output
4



-----Note-----

Value 4 is achieved at such an arrangement, for example: 1, 2, 3, 5, 15. Thus, you can make everything feel not disappointed except for the person with time 5.
user: Today is Devu's birthday. For celebrating the occasion, he bought n sweets from the nearby market. He has invited his f friends. He would like to distribute the sweets among them. As he is a nice guy and the occasion is great, he doesn't want any friend to be sad, so he would ensure to give at least one sweet to each friend. 

He wants to celebrate it in a unique style, so he would like to ensure following condition for the distribution of sweets. Assume that he has distributed n sweets to his friends such that i^{th} friend is given a_{i} sweets. He wants to make sure that there should not be any positive integer x > 1, which divides every a_{i}.

Please find the number of ways he can distribute sweets to his friends in the required way. Note that the order of distribution is important, for example [1, 2] and [2, 1] are distinct distributions. As the answer could be very large, output answer modulo 1000000007 (10^9 + 7).

To make the problem more interesting, you are given q queries. Each query contains an n, f pair. For each query please output the required number of ways modulo 1000000007 (10^9 + 7).


-----Input-----

The first line contains an integer q representing the number of queries (1 ≤ q ≤ 10^5). Each of the next q lines contains two space space-separated integers n, f (1 ≤ f ≤ n ≤ 10^5).


-----Output-----

For each query, output a single integer in a line corresponding to the answer of each query.


-----Examples-----
Input
5
6 2
7 2
6 3
6 4
7 4

Output
2
6
9
10
20



-----Note-----

For first query: n = 6, f = 2. Possible partitions are [1, 5] and [5, 1].

For second query: n = 7, f = 2. Possible partitions are [1, 6] and [2, 5] and [3, 4] and [4, 3] and [5, 3] and [6, 1]. So in total there are 6 possible ways of partitioning.
user: Vasiliy has an exam period which will continue for n days. He has to pass exams on m subjects. Subjects are numbered from 1 to m.

About every day we know exam for which one of m subjects can be passed on that day. Perhaps, some day you can't pass any exam. It is not allowed to pass more than one exam on any day. 

On each day Vasiliy can either pass the exam of that day (it takes the whole day) or prepare all day for some exam or have a rest. 

About each subject Vasiliy know a number a_{i} — the number of days he should prepare to pass the exam number i. Vasiliy can switch subjects while preparing for exams, it is not necessary to prepare continuously during a_{i} days for the exam number i. He can mix the order of preparation for exams in any way.

Your task is to determine the minimum number of days in which Vasiliy can pass all exams, or determine that it is impossible. Each exam should be passed exactly one time. 


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10^5) — the number of days in the exam period and the number of subjects. 

The second line contains n integers d_1, d_2, ..., d_{n} (0 ≤ d_{i} ≤ m), where d_{i} is the number of subject, the exam of which can be passed on the day number i. If d_{i} equals 0, it is not allowed to pass any exams on the day number i. 

The third line contains m positive integers a_1, a_2, ..., a_{m} (1 ≤ a_{i} ≤ 10^5), where a_{i} is the number of days that are needed to prepare before passing the exam on the subject i.


-----Output-----

Print one integer — the minimum number of days in which Vasiliy can pass all exams. If it is impossible, print -1.


-----Examples-----
Input
7 2
0 1 0 2 1 0 2
2 1

Output
5

Input
10 3
0 0 1 2 3 0 2 0 1 2
1 1 4

Output
9

Input
5 1
1 1 1 1 1
5

Output
-1



-----Note-----

In the first example Vasiliy can behave as follows. On the first and the second day he can prepare for the exam number 1 and pass it on the fifth day, prepare for the exam number 2 on the third day and pass it on the fourth day.

In the second example Vasiliy should prepare for the exam number 3 during the first four days and pass it on the fifth day. Then on the sixth day he should prepare for the exam number 2 and then pass it on the seventh day. After that he needs to prepare for the exam number 1 on the eighth day and pass it on the ninth day. 

In the third example Vasiliy can't pass the only exam because he hasn't anough time to prepare for it.
user: Lee is used to finish his stories in a stylish way, this time he barely failed it, but Ice Bear came and helped him. Lee is so grateful for it, so he decided to show Ice Bear his new game called "Critic"...

The game is a one versus one game. It has $t$ rounds, each round has two integers $s_i$ and $e_i$ (which are determined and are known before the game begins, $s_i$ and $e_i$ may differ from round to round). The integer $s_i$ is written on the board at the beginning of the corresponding round. 

The players will take turns. Each player will erase the number on the board (let's say it was $a$) and will choose to write either $2 \cdot a$ or $a + 1$ instead. Whoever writes a number strictly greater than $e_i$ loses that round and the other one wins that round.

Now Lee wants to play "Critic" against Ice Bear, for each round he has chosen the round's $s_i$ and $e_i$ in advance. Lee will start the first round, the loser of each round will start the next round.

The winner of the last round is the winner of the game, and the loser of the last round is the loser of the game.

Determine if Lee can be the winner independent of Ice Bear's moves or not. Also, determine if Lee can be the loser independent of Ice Bear's moves or not.


-----Input-----

The first line contains the integer $t$ ($1 \le t \le 10^5$) — the number of rounds the game has. 

Then $t$ lines follow, each contains two integers $s_i$ and $e_i$ ($1 \le s_i \le e_i \le 10^{18}$) — the $i$-th round's information.

The rounds are played in the same order as given in input, $s_i$ and $e_i$ for all rounds are known to everyone before the game starts.


-----Output-----

Print two integers.

The first one should be 1 if Lee can be the winner independent of Ice Bear's moves, and 0 otherwise.

The second one should be 1 if Lee can be the loser independent of Ice Bear's moves, and 0 otherwise.


-----Examples-----
Input
3
5 8
1 4
3 10

Output
1 1

Input
4
1 2
2 3
3 4
4 5

Output
0 0

Input
1
1 1

Output
0 1

Input
2
1 9
4 5

Output
0 0

Input
2
1 2
2 8

Output
1 0

Input
6
216986951114298167 235031205335543871
148302405431848579 455670351549314242
506251128322958430 575521452907339082
1 768614336404564650
189336074809158272 622104412002885672
588320087414024192 662540324268197150

Output
1 0



-----Note-----

Remember, whoever writes an integer greater than $e_i$ loses.
user: 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.
user: Grandma Laura came to the market to sell some apples. During the day she sold all the apples she had. But grandma is old, so she forgot how many apples she had brought to the market.

She precisely remembers she had n buyers and each of them bought exactly half of the apples she had at the moment of the purchase and also she gave a half of an apple to some of them as a gift (if the number of apples at the moment of purchase was odd), until she sold all the apples she had.

So each buyer took some integral positive number of apples, but maybe he didn't pay for a half of an apple (if the number of apples at the moment of the purchase was odd).

For each buyer grandma remembers if she gave a half of an apple as a gift or not. The cost of an apple is p (the number p is even).

Print the total money grandma should have at the end of the day to check if some buyers cheated her.


-----Input-----

The first line contains two integers n and p (1 ≤ n ≤ 40, 2 ≤ p ≤ 1000) — the number of the buyers and the cost of one apple. It is guaranteed that the number p is even.

The next n lines contains the description of buyers. Each buyer is described with the string half if he simply bought half of the apples and with the string halfplus if grandma also gave him a half of an apple as a gift.

It is guaranteed that grandma has at least one apple at the start of the day and she has no apples at the end of the day.


-----Output-----

Print the only integer a — the total money grandma should have at the end of the day.

Note that the answer can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.


-----Examples-----
Input
2 10
half
halfplus

Output
15

Input
3 10
halfplus
halfplus
halfplus

Output
55



-----Note-----

In the first sample at the start of the day the grandma had two apples. First she sold one apple and then she sold a half of the second apple and gave a half of the second apple as a present to the second buyer.
user: Eugeny has n cards, each of them has exactly one integer written on it. Eugeny wants to exchange some cards with Nikolay so that the number of even integers on his cards would equal the number of odd integers, and that all these numbers would be distinct. 

Nikolay has m cards, distinct numbers from 1 to m are written on them, one per card. It means that Nikolay has exactly one card with number 1, exactly one card with number 2 and so on. 

A single exchange is a process in which Eugeny gives one card to Nikolay and takes another one from those Nikolay has. Your task is to find the minimum number of card exchanges and determine which cards Eugeny should exchange.


-----Input-----

The first line contains two integers n and m (2 ≤ n ≤ 2·10^5, 1 ≤ m ≤ 10^9) — the number of cards Eugeny has and the number of cards Nikolay has. It is guaranteed that n is even.

The second line contains a sequence of n positive integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — the numbers on Eugeny's cards.


-----Output-----

If there is no answer, print -1.

Otherwise, in the first line print the minimum number of exchanges. In the second line print n integers — Eugeny's cards after all the exchanges with Nikolay. The order of cards should coincide with the card's order in the input data. If the i-th card wasn't exchanged then the i-th number should coincide with the number from the input data. Otherwise, it is considered that this card was exchanged, and the i-th number should be equal to the number on the card it was exchanged to.

If there are multiple answers, it is allowed to print any of them.


-----Examples-----
Input
6 2
5 6 7 9 4 5

Output
1
5 6 7 9 4 2 

Input
8 6
7 7 7 7 8 8 8 8

Output
6
7 2 4 6 8 1 3 5 

Input
4 1
4 2 1 10

Output
-1
user: The next "Data Structures and Algorithms" lesson will be about Longest Increasing Subsequence (LIS for short) of a sequence. For better understanding, Nam decided to learn it a few days before the lesson.

Nam created a sequence a consisting of n (1 ≤ n ≤ 10^5) elements a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5). A subsequence a_{i}_1, a_{i}_2, ..., a_{i}_{k} where 1 ≤ i_1 < i_2 < ... < i_{k} ≤ n is called increasing if a_{i}_1 < a_{i}_2 < a_{i}_3 < ... < a_{i}_{k}. An increasing subsequence is called longest if it has maximum length among all increasing subsequences. 

Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes i (1 ≤ i ≤ n), into three groups: group of all i such that a_{i} belongs to no longest increasing subsequences. group of all i such that a_{i} belongs to at least one but not every longest increasing subsequence. group of all i such that a_{i} belongs to every longest increasing subsequence. 

Since the number of longest increasing subsequences of a may be very large, categorizing process is very difficult. Your task is to help him finish this job.


-----Input-----

The first line contains the single integer n (1 ≤ n ≤ 10^5) denoting the number of elements of sequence a.

The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5).


-----Output-----

Print a string consisting of n characters. i-th character should be '1', '2' or '3' depending on which group among listed above index i belongs to.


-----Examples-----
Input
1
4

Output
3

Input
4
1 3 2 5

Output
3223

Input
4
1 5 2 3

Output
3133



-----Note-----

In the second sample, sequence a consists of 4 elements: {a_1, a_2, a_3, a_4} = {1, 3, 2, 5}. Sequence a has exactly 2 longest increasing subsequences of length 3, they are {a_1, a_2, a_4} = {1, 3, 5} and {a_1, a_3, a_4} = {1, 2, 5}.

In the third sample, sequence a consists of 4 elements: {a_1, a_2, a_3, a_4} = {1, 5, 2, 3}. Sequence a have exactly 1 longest increasing subsequence of length 3, that is {a_1, a_3, a_4} = {1, 2, 3}.