vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Xenia and Tree

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Xenia the programmer has a tree consisting of *n* nodes. We will consider the tree nodes indexed from 1 to *n*. We will also consider the first node to be initially painted red, and the other nodes — to be painted blue.

The distance between two tree nodes *v* and *u* is the number of edges in the shortest path between *v* and *u*.

Xenia needs to learn how to quickly execute queries of two types:
 1.  paint a specified blue node in red; 1.  calculate which red node is the closest to the given one and print the shortest distance to the closest red node. 
Your task is to write a program which will execute the described queries.

Input Specification:
The first line contains two integers *n* and *m* (2<=≤<=*n*<=≤<=105,<=1<=≤<=*m*<=≤<=105) — the number of nodes in the tree and the number of queries. Next *n*<=-<=1 lines contain the tree edges, the *i*-th line contains a pair of integers *a**i*,<=*b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*,<=*a**i*<=≠<=*b**i*) — an edge of the tree.

Next *m* lines contain queries. Each query is specified as a pair of integers *t**i*,<=*v**i* (1<=≤<=*t**i*<=≤<=2,<=1<=≤<=*v**i*<=≤<=*n*). If *t**i*<==<=1, then as a reply to the query we need to paint a blue node *v**i* in red. If *t**i*<==<=2, then we should reply to the query by printing the shortest distance from some red node to node *v**i*.

It is guaranteed that the given graph is a tree and that all queries are correct.

Output Specification:
For each second type query print the reply in a single line.

Demo Input:
['5 4\n1 2\n2 3\n2 4\n4 5\n2 1\n2 5\n1 2\n2 5\n']

Demo Output:
['0\n3\n2\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Calculating Function

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
For a positive integer *n* let's define a function *f*:

*f*(*n*)<==<=<=-<=1<=+<=2<=-<=3<=+<=..<=+<=(<=-<=1)*n**n* 

Your task is to calculate *f*(*n*) for a given integer *n*.

Input Specification:
The single line contains the positive integer *n* (1<=≤<=*n*<=≤<=1015).

Output Specification:
Print *f*(*n*) in a single line.

Demo Input:
['4\n', '5\n']

Demo Output:
['2\n', '-3\n']

Note:
*f*(4) =  - 1 + 2 - 3 + 4 = 2

*f*(5) =  - 1 + 2 - 3 + 4 - 5 =  - 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your favourite social media website is changing their policy on login password validation: a slight error when logging in is now acceptable! In particular, assuming the password you chose when creating the account is $S$, a password $P$ entered while logging in will be accepted if any of the following conditions are met:
 - $P$ and $S$ are identical;
 - $S$ can be formed from $P$ by prepending a single digit (0–9);
 - $S$ can be formed from $P$ by appending a single digit;
 - $S$ is equal to $P$ after reversing the case of all letters in $P$.

To reverse the case of a string, replace all uppercase letters with their equivalent lowercase letters, and all lowercase letters with their equivalent uppercase letters, while leaving all other characters the same. For example, the case-reversal of pa55WORD is PA55word.

Any other attempted password $P$ will be rejected. So for example, if $S$ is c0deninja5, then c0deninja will be accepted, but not C0deninja5 or c0deninja51.

Write a program which, given alphanumeric strings $S$ and $P$, determines whether $P$ should be accepted.

-----Input-----
The first line of the input is the string $S$, the stored password, and the second line of input is the password $P$ that a user has entered while attempting to log in. Each string consists of only digits 0–9, lowercase letters a–z, and uppercase letters A–Z. The strings won’t contain spaces or any other extraneous characters, and will each contain at least one and at most $101$ characters.

-----Output-----
Print Yes if $P$ should be accepted according to the above rules, and No otherwise.

-----Examples-----
Sample Input:
123
123a
Sample Output:
No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string S consisting of a,b and c. Find the number of strings that can be possibly obtained by repeatedly performing the following operation zero or more times, modulo 998244353:
 - Choose an integer i such that 1\leq i\leq |S|-1 and the i-th and (i+1)-th characters in S are different. Replace each of the i-th and (i+1)-th characters in S with the character that differs from both of them (among a, b and c).

-----Constraints-----
 - 2 \leq |S| \leq 2 × 10^5
 - S consists of a, b and c.

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
Print the number of strings that can be possibly obtained by repeatedly performing the operation, modulo 998244353.

-----Sample Input-----
abc

-----Sample Output-----
3

abc, aaa and ccc can be obtained.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 Dudka has `n` details. He must keep exactly 3 of them.

 To do this, he performs the following operations until he has only 3 details left:
```
He numbers them.
He keeps those with either odd or even numbers and throws the others away.```

 Dudka wants to know how many ways there are to get exactly 3 details. Your task is  to help him calculate it.

# Example

 For `n = 6`, the output should be `2`.
 ```
Dudka has 6 details, numbered 1 2 3 4 5 6. 
He can keep either details with numbers 1, 3, 5, 
or with numbers 2, 4, 6. 
Both options leave him with 3 details, 
so the answer is 2.```

 For `n = 7`, the output should be `1`.
 ```
Dudka has 7 details, numbered 1 2 3 4 5 6 7. 
He can keep either details 1 3 5 7, or details 2 4 6. 
If he keeps details 1 3 5 7 , 
he won't be able to get 3 details in the future, 
because at the next step he will number them 1 2 3 4 
and will have to keep either details 1 3, or 2 4, 
only two details anyway. 
That's why he must keep details 2 4 6 at the first step, 
so the answer is 1.```

# Input/Output


 - `[input]` integer `n`

  `3 ≤ n ≤ 10^9`


 - `[output]` an integer

  The number of ways to get exactly 3 details.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
**Introduction**
 Little Petya very much likes sequences. However, recently he received a sequence as a gift from his mother.
 Petya didn't like it at all! He decided to make a single replacement. After this replacement, Petya would like to the sequence in increasing order.
 He asks himself: What is the lowest possible value I could have got after making the replacement and sorting the sequence?

**About the replacement**
 Choose exactly one element from the sequence and replace it with another integer > 0. You are **not allowed** to replace a number with itself, or to change no number at all.

**Task**
 Find the lowest possible sequence after performing a valid replacement, and sorting the sequence.

**Input:**
 Input contains sequence with `N` integers. All elements of the sequence > 0. The sequence will never be empty.

**Output:**
 Return sequence with `N` integers — which includes the lowest possible values of each sequence element, after the single replacement and sorting has been performed.

**Examples**:
```
([1,2,3,4,5])  =>  [1,1,2,3,4]
([4,2,1,3,5])  =>  [1,1,2,3,4]
([2,3,4,5,6])  =>  [1,2,3,4,5]
([2,2,2])      =>  [1,2,2]
([42])         =>  [1]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer $n$ ($n \ge 0$) represented with $k$ digits in base (radix) $b$. So,

$$n = a_1 \cdot b^{k-1} + a_2 \cdot b^{k-2} + \ldots a_{k-1} \cdot b + a_k.$$

For example, if $b=17, k=3$ and $a=[11, 15, 7]$ then $n=11\cdot17^2+15\cdot17+7=3179+255+7=3441$.

Determine whether $n$ is even or odd.


-----Input-----

The first line contains two integers $b$ and $k$ ($2\le b\le 100$, $1\le k\le 10^5$) — the base of the number and the number of digits.

The second line contains $k$ integers $a_1, a_2, \ldots, a_k$ ($0\le a_i < b$) — the digits of $n$.

The representation of $n$ contains no unnecessary leading zero. That is, $a_1$ can be equal to $0$ only if $k = 1$.


-----Output-----

Print "even" if $n$ is even, otherwise print "odd".

You can print each letter in any case (upper or lower).


-----Examples-----
Input
13 3
3 2 7

Output
even

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

Output
odd

Input
99 5
32 92 85 74 4

Output
odd

Input
2 2
1 0

Output
even



-----Note-----

In the first example, $n = 3 \cdot 13^2 + 2 \cdot 13 + 7 = 540$, which is even.

In the second example, $n = 123456789$ is odd.

In the third example, $n = 32 \cdot 99^4 + 92 \cdot 99^3 + 85 \cdot 99^2 + 74 \cdot 99 + 4 = 3164015155$ is odd.

In the fourth example $n = 2$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of integer numbers. Calculate the sum of its elements.

Input

The first line of the input contains an integer n (1 ≤ n ≤ 100) — the size of the array. Next n lines contain the elements of the array, one per line. Each element is an integer between 1 and 100, inclusive.

Output

Output the sum of the elements of the array.

Examples

Input

5
1
2
3
4
5


Output

15


Input

7
100
5
45
86
14
20
30


Output

300

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The country of Byalechinsk is running elections involving n candidates. The country consists of m cities. We know how many people in each city voted for each candidate.

The electoral system in the country is pretty unusual. At the first stage of elections the votes are counted for each city: it is assumed that in each city won the candidate who got the highest number of votes in this city, and if several candidates got the maximum number of votes, then the winner is the one with a smaller index.

At the second stage of elections the winner is determined by the same principle over the cities: the winner of the elections is the candidate who won in the maximum number of cities, and among those who got the maximum number of cities the winner is the one with a smaller index.

Determine who will win the elections.


-----Input-----

The first line of the input contains two integers n, m (1 ≤ n, m ≤ 100) — the number of candidates and of cities, respectively.

Each of the next m lines contains n non-negative integers, the j-th number in the i-th line a_{ij} (1 ≤ j ≤ n, 1 ≤ i ≤ m, 0 ≤ a_{ij} ≤ 10^9) denotes the number of votes for candidate j in city i.

It is guaranteed that the total number of people in all the cities does not exceed 10^9.


-----Output-----

Print a single number — the index of the candidate who won the elections. The candidates are indexed starting from one.


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

Output
2
Input
3 4
10 10 3
5 1 6
2 2 2
1 5 7

Output
1


-----Note-----

Note to the first sample test. At the first stage city 1 chosen candidate 3, city 2 chosen candidate 2, city 3 chosen candidate 2. The winner is candidate 2, he gained 2 votes.

Note to the second sample test. At the first stage in city 1 candidates 1 and 2 got the same maximum number of votes, but candidate 1 has a smaller index, so the city chose candidate 1. City 2 chosen candidate 3. City 3 chosen candidate 1, due to the fact that everyone has the same number of votes, and 1 has the smallest index. City 4 chosen the candidate 3. On the second stage the same number of cities chose candidates 1 and 3. The winner is candidate 1, the one with the smaller index.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Now that Heidi knows that she can assign Rebel spaceships to bases (recall the easy subtask), she is asking you: how exactly to do this? Now, given positions of N spaceships and N bases on a plane, your task is to connect spaceships and bases with line segments so that: 

  * The segments do not intersect. 
  * Such a connection forms a perfect matching. 

Input

The first line contains an integer N (1 ≤ n ≤ 10000). For 1 ≤ i ≤ N, the i + 1-th line contains two integers xi and yi (|xi|, |yi| ≤ 10000) denoting the coordinates of the i-th spaceship. The following N lines have the same format, denoting the position of bases. It is guaranteed that no two points coincide and no three points are on the same line.

Output

The output should have N lines. The i-th line should contain an integer pi, the index of the base to which the i-th spaceship is connected. The sequence p1, ..., pN should form a permutation of 1, ..., N.

It is guaranteed that a solution exists. If there are multiple solutions, you can output any one of them.

Example

Input

4
6 6
5 1
2 4
4 0
5 4
1 2
2 1
3 5


Output

4
1
2
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The medians of a triangle are the segments that unit the vertices with the midpoint of their opposite sides.
The three medians of a triangle intersect at the same point, called the barycenter or the centroid.
Given a triangle, defined by the cartesian coordinates of its vertices we need to localize its barycenter or centroid.

The function ```bar_triang() or barTriang or bar-triang```, receives the coordinates of the three vertices ```A, B and C ``` as three different arguments and outputs the coordinates of the barycenter ```O``` in an array ```[xO, yO]```

This is how our asked function should work:
the result of the coordinates should be expressed up to four decimals, (rounded result).

You know that the coordinates of the barycenter are given by the following formulas.



For additional information about this important point of a triangle see at: (https://en.wikipedia.org/wiki/Centroid)

Let's see some cases:
```python
bar_triang([4, 6], [12, 4], [10, 10]) ------> [8.6667, 6.6667]

bar_triang([4, 2], [12, 2], [6, 10] ------> [7.3333, 4.6667]
```
The given points form a real or a degenerate triangle but in each case the above formulas can be used.

Enjoy it and happy coding!!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vova is playing a computer game. There are in total $n$ turns in the game and Vova really wants to play all of them. The initial charge of his laptop battery (i.e. the charge before the start of the game) is $k$.

During each turn Vova can choose what to do:   If the current charge of his laptop battery is strictly greater than $a$, Vova can just play, and then the charge of his laptop battery will decrease by $a$;  if the current charge of his laptop battery is strictly greater than $b$ ($b<a$), Vova can play and charge his laptop, and then the charge of his laptop battery will decrease by $b$;  if the current charge of his laptop battery is less than or equal to $a$ and $b$ at the same time then Vova cannot do anything and loses the game. 

Regardless of Vova's turns the charge of the laptop battery is always decreases.

Vova wants to complete the game (Vova can complete the game if after each of $n$ turns the charge of the laptop battery is strictly greater than $0$). Vova has to play exactly $n$ turns. Among all possible ways to complete the game, Vova wants to choose the one where the number of turns when he just plays (first type turn) is the maximum possible. It is possible that Vova cannot complete the game at all.

Your task is to find out the maximum possible number of turns Vova can just play (make the first type turn) or report that Vova cannot complete the game.

You have to answer $q$ independent queries.


-----Input-----

The first line of the input contains one integer $q$ ($1 \le q \le 10^5$) — the number of queries. Each query is presented by a single line.

The only line of the query contains four integers $k, n, a$ and $b$ ($1 \le k, n \le 10^9, 1 \le b < a \le 10^9$) — the initial charge of Vova's laptop battery, the number of turns in the game and values $a$ and $b$, correspondingly.


-----Output-----

For each query print one integer: -1 if Vova cannot complete the game or the maximum number of turns Vova can just play (make the first type turn) otherwise.


-----Example-----
Input
6
15 5 3 2
15 5 4 3
15 5 2 1
15 5 5 1
16 7 5 2
20 5 7 3

Output
4
-1
5
2
0
1



-----Note-----

In the first example query Vova can just play $4$ turns and spend $12$ units of charge and then one turn play and charge and spend $2$ more units. So the remaining charge of the battery will be $1$.

In the second example query Vova cannot complete the game because even if he will play and charge the battery during each turn then the charge of the laptop battery will be $0$ after the last turn.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Minimum Sum

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petya has *n* positive integers *a*1,<=*a*2,<=...,<=*a**n*. 

His friend Vasya decided to joke and replaced all digits in Petya's numbers with a letters. He used the lowercase letters of the Latin alphabet from 'a' to 'j' and replaced all digits 0 with one letter, all digits 1 with another letter and so on. For any two different digits Vasya used distinct letters from 'a' to 'j'.

Your task is to restore Petya's numbers. The restored numbers should be positive integers without leading zeros. Since there can be multiple ways to do it, determine the minimum possible sum of all Petya's numbers after the restoration. It is guaranteed that before Vasya's joke all Petya's numbers did not have leading zeros.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=1<=000) — the number of Petya's numbers.

Each of the following lines contains non-empty string *s**i* consisting of lowercase Latin letters from 'a' to 'j' — the Petya's numbers after Vasya's joke. The length of each string does not exceed six characters.

Output Specification:
Determine the minimum sum of all Petya's numbers after the restoration. The restored numbers should be positive integers without leading zeros. It is guaranteed that the correct restore (without leading zeros) exists for all given tests.

Demo Input:
['3\nab\nde\naj\n', '5\nabcdef\nghij\nbdef\naccbd\ng\n', '3\naa\njj\naa\n']

Demo Output:
['47\n', '136542\n', '44\n']

Note:
In the first example, you need to replace the letter 'a' with the digit 1, the letter 'b' with the digit 0, the letter 'd' with the digit 2, the letter 'e' with the digit 3, and the letter 'j' with the digit 4. So after the restoration numbers will look like [10, 23, 14]. The sum of them is equal to 47, which is the minimum possible sum of the numbers after the correct restoration.

In the second example the numbers after the restoration can look like: [120468, 3579, 2468, 10024, 3]. 

In the second example the numbers after the restoration can look like: [11, 22, 11].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice is a big fan of volleyball and especially of the very strong "Team A".

Volleyball match consists of up to five sets. During each set teams score one point for winning a ball. The first four sets are played until one of the teams scores at least 25 points and the fifth set is played until one of the teams scores at least 15 points. Moreover, if one of the teams scores 25 (or 15 in the fifth set) points while the other team scores 24 (or 14 in the fifth set), the set is played until the absolute difference between teams' points becomes two. The match ends when one of the teams wins three sets. The match score is the number of sets won by each team.

Alice found a book containing all the results of all matches played by "Team A". The book is old, and some parts of the book became unreadable. Alice can not read the information on how many sets each of the teams won, she can not read the information on how many points each of the teams scored in each set, she even does not know the number of sets played in a match. The only information she has is the total number of points scored by each of the teams in all the sets during a single match.

Alice wonders what is the best match score "Team A" could achieve in each of the matches. The bigger is the difference between the number of sets won by "Team A" and their opponent, the better is the match score. Find the best match score or conclude that no match could end like that. If there is a solution, then find any possible score for each set that results in the best match score.

Input

The first line contains a single integer m (1 ≤ m ≤ 50 000) — the number of matches found by Alice in the book.

Each of the next m lines contains two integers a and b (0 ≤ a, b ≤ 200) — the number of points scored by "Team A" and the number of points scored by their opponents respectively.

Output

Output the solution for every match in the same order as they are given in the input. If the teams could not score a and b points respectively, output "Impossible".

Otherwise, output the match score formatted as "x:y", where x is the number of sets won by "Team A" and y is the number of sets won by their opponent. 

The next line should contain the set scores in the order they were played. Each set score should be printed in the same format as the match score, with x being the number of points scored by "Team A" in this set, and y being the number of points scored by their opponent.

Example

Input


6
75 0
90 90
20 0
0 75
78 50
80 100


Output


3:0
25:0 25:0 25:0
3:1
25:22 25:22 15:25 25:21
Impossible
0:3
0:25 0:25 0:25
3:0
25:11 28:26 25:13
3:2
25:17 0:25 25:22 15:25 15:11

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This question is designed to help you get a better understanding of basic heap operations.  

There are $3$ types of query:

"$1$ $\boldsymbol{\nu}$"  - Add an element $\boldsymbol{\nu}$ to the heap.  
"$2$ $\boldsymbol{\nu}$"  - Delete the element $\boldsymbol{\nu}$ from the heap.  
"$3$" - Print the minimum of all the elements in the heap.

NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct elements will be in the heap.

Input Format

The first line contains the number of queries, $Q$. 

Each of the next $Q$ lines contains one of the $3$ types of query.   

Constraints 

$1\leq Q\leq10^5$ 

$-10^9\leq v\leq10^9$

Output Format

For each query of type $3$, print the minimum value on a single line.  

Sample Input
STDIN       Function
-----       --------
5           Q = 5
1 4         insert 4
1 9         insert 9
3           print minimum
2 4         delete 4
3           print minimum

Sample Output
4  
9 

Explanation

After the first $2$ queries, the heap contains {$4,9$}. Printing the minimum gives $\begin{array}{c}4\end{array}$ as the output. Then, the $4^{th}$ query deletes $\begin{array}{c}4\end{array}$ from the heap, and the $5^{th}$ query gives $\mbox{9}$ as the output.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S. For each index i(1<=i<=N-1), erase it if s[i] is equal to s[i-1] in the string.
Example 1:
Input:
S = aabb
Output:  ab 
Explanation: 'a' at 2nd position is
appearing 2nd time consecutively.
Similiar explanation for b at
4th position.
Example 2:
Input:
S = aabaa
Output:  aba
Explanation: 'a' at 2nd position is
appearing 2nd time consecutively.
'a' at fifth position is appearing
2nd time consecutively.
 
Your Task:
You dont need to read input or print anything. Complete the function removeConsecutiveCharacter() which accepts a string as input parameter and returns modified string. 
 
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(|S|).
 
Constraints:
1<=|S|<=10^{5}
All characters are lowercase alphabets.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.