vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Hiasat registered a new account in NeckoForces and when his friends found out about that, each one of them asked to use his name as Hiasat's handle.

Luckily for Hiasat, he can change his handle in some points in time. Also he knows the exact moments friends will visit his profile page. Formally, you are given a sequence of events of two types:

  $1$ — Hiasat can change his handle.  $2$ $s$ — friend $s$ visits Hiasat's profile. 

The friend $s$ will be happy, if each time he visits Hiasat's profile his handle would be $s$.

Hiasat asks you to help him, find the maximum possible number of happy friends he can get.


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 10^5, 1 \le m \le 40$) — the number of events and the number of friends.

Then $n$ lines follow, each denoting an event of one of two types:   $1$ — Hiasat can change his handle.  $2$ $s$ — friend $s$ ($1 \le |s| \le 40$) visits Hiasat's profile. 

It's guaranteed, that each friend's name consists only of lowercase Latin letters.

It's guaranteed, that the first event is always of the first type and each friend will visit Hiasat's profile at least once.


-----Output-----

Print a single integer — the maximum number of happy friends.


-----Examples-----
Input
5 3
1
2 motarack
2 mike
1
2 light

Output
2

Input
4 3
1
2 alice
2 bob
2 tanyaromanova

Output
1



-----Note-----

In the first example, the best way is to change the handle to the "motarack" in the first event and to the "light" in the fourth event. This way, "motarack" and "light" will be happy, but "mike" will not.

In the second example, you can choose either "alice", "bob" or "tanyaromanova" and only that friend will be happy.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Learning to code around your full time job is taking over your life. You realise that in order to make significant steps quickly, it would help to go to a coding bootcamp in London.

Problem is, many of them cost a fortune, and those that don't still involve a significant amount of time off work - who will pay your mortgage?!

To offset this risk, you decide that rather than leaving work totally, you will request a sabbatical so that you can go back to work post bootcamp and be paid while you look for your next role.

You need to approach your boss. Her decision will be based on three parameters:

val=your value to the organisation
happiness=her happiness level at the time of asking and finally
The numbers of letters from 'sabbatical' that are present in string `s`.

Note that if `s` contains three instances of the letter 'l', that still scores three points, even though there is only one in the word sabbatical.

If the sum of the three parameters (as described above) is > 22, return 'Sabbatical! Boom!', else return 'Back to your desk, boy.'.

~~~if:c
NOTE: For the C translation you should return a string literal.
~~~

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have three stones at points (0, 0), (1,0), and (0,1) on a two-dimensional plane.
These three stones are said to form an L when they satisfy the following conditions:
 - Each of the stones is at integer coordinates.
 - Each of the stones is adjacent to another stone. (That is, for each stone, there is another stone whose distance from that stone is 1.)
 - The three stones do not lie on the same line.
Particularly, the initial arrangement of the stone - (0, 0), (1,0), and (0,1) - forms an L.
You can do the following operation any number of times: choose one of the stones and move it to any position. However, after each operation, the stones must form an L.
You want to do as few operations as possible to put stones at points (ax, ay), (bx, by), and (cx, cy). How many operations do you need to do this?
It is guaranteed that the desired arrangement of stones - (ax, ay), (bx, by), and (cx, cy) - forms an L. Under this condition, it is always possible to achieve the objective with a finite number of operations.
You will be given T cases of this problem. Solve each of them.

-----Notes-----
We assume that the three stones are indistinguishable. For example, the stone that is initially at point (0,0) may be at any of the points (ax, ay), (bx, by), and (cx, cy) in the end.

-----Constraints-----
 - 1 \leq T \leq 10^3
 - |ax|,|ay|,|bx|,|by|,|cx|,|cy| \leq 10^9
 - The desired arrangement of stones - (ax, ay), (bx, by), and (cx, cy) - forms an L.

-----Input-----
Input is given from Standard Input in the following format:
T
\text{case}_1
\vdots
\text{case}_T

Each case is in the following format:
ax ay bx by cx cy

-----Output-----
Print T values. The i-th value should be the minimum number of operations for \text{case}_i.

-----Sample Input-----
1
3 2 2 2 2 1

-----Sample Output-----
4

Let us use # to represent a stone.
You can move the stones to the specified positions with four operations, as follows:
....    ....    ....    ..#.    ..##
#... -> ##.. -> .##. -> .##. -> ..#.
##..    .#..    .#..    ....    ....

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pak Chanek plans to build a garage. He wants the garage to consist of a square and a right triangle that are arranged like the following illustration.

Define $a$ and $b$ as the lengths of two of the sides in the right triangle as shown in the illustration. An integer $x$ is suitable if and only if we can construct a garage with assigning positive integer values for the lengths $a$ and $b$ ($a<b$) so that the area of the square at the bottom is exactly $x$. As a good friend of Pak Chanek, you are asked to help him find the $N$-th smallest suitable number.


-----Input-----

The only line contains a single integer $N$ ($1 \leq N \leq 10^9$).


-----Output-----

An integer that represents the $N$-th smallest suitable number.


-----Examples-----

Input
3
Output
7


-----Note-----

The $3$-rd smallest suitable number is $7$. A square area of $7$ can be obtained by assigning $a=3$ and $b=4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of digits (values are from 0 to 9), find the minimum possible sum of two numbers formed from digits of the array. All digits of the given array must be used to form the two numbers.
Any combination of digits may be used to form the two numbers to be summed.  Leading zeroes are permitted.
If forming two numbers is impossible (i.e. when n==0) then the "sum" is the value of the only number that can be formed.
 
 
Example 1:
Input:
N = 6
arr[] = {6, 8, 4, 5, 2, 3}
Output:
604
Explanation:
The minimum sum is formed by numbers 
358 and 246
 
Example 2:
Input:
N = 5
arr[] = {5, 3, 0, 7, 4}
Output:
82
Explanation:
The minimum sum is formed by numbers 
35 and 047
Your Task:
You don't have to print anything, printing is done by the driver code itself. Your task is to complete the function minSum() which takes the array A[] and its size N as inputs and returns the required sum.
Expected Time Complexity: O(N. log(N))
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 35
0 ≤ A[] ≤ 9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Related to MrZizoScream's Product Array kata. You might want to solve that one first :)

```if:javascript
**Note:** Node 10 has now been enabled, and you can now use its BigInt capabilities if you wish, though your resulting array must still contain strings (e.g. "99999999999", not 9999999999n)

Pre-node 10: You will need to use the BigNumber.js library! Please use `.toFixed(0)` or `.toPrecision()` to round instead of `.toString(10)`, as the latter is _very_ slow
```

This is an adaptation of a problem I came across on LeetCode. 

Given an array of numbers, your task is to return a new array where each index (`new_array[i]`) is equal to the product of the original array, except for the number at that index (`array[i]`).

**Two things to keep in mind:**

* Zeroes will be making their way into some of the arrays you are given
* O(n^2) solutions will not pass.

Examples:

**Note**: All inputs will be valid arrays of nonzero length.

Have fun! Please upvote if you enjoyed :)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Thought it is already the XXI century, the Mass Media isn't very popular in Walrusland. The cities get news from messengers who can only travel along roads. The network of roads in Walrusland is built so that it is possible to get to any city from any other one in exactly one way, and the roads' lengths are equal.

The North Pole governor decided to carry out an information reform. Several cities were decided to be chosen and made regional centers. Maintaining a region center takes k fishlars (which is a local currency) per year. It is assumed that a regional center always has information on the latest news.

For every city which is not a regional center, it was decided to appoint a regional center which will be responsible for keeping this city informed. In that case the maintenance costs will be equal to dlen fishlars per year, where len is the distance from a city to the corresponding regional center, measured in the number of roads along which one needs to go.

Your task is to minimize the costs to carry out the reform.

Input

The first line contains two given numbers n and k (1 ≤ n ≤ 180, 1 ≤ k ≤ 105).

The second line contains n - 1 integers di, numbered starting with 1 (di ≤ di + 1, 0 ≤ di ≤ 105).

Next n - 1 lines contain the pairs of cities connected by a road.

Output

On the first line print the minimum number of fishlars needed for a year's maintenance. On the second line print n numbers, where the i-th number will represent the number of the regional center, appointed to the i-th city. If the i-th city is a regional center itself, then you should print number i.

If there are several solutions to that problem, print any of them.

Examples

Input

8 10
2 5 9 11 15 19 20
1 4
1 3
1 7
4 6
2 8
2 3
3 5


Output

38
3 3 3 4 3 4 3 3 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a_1, a_2, \dots, a_n$ where all $a_i$ are integers and greater than $0$.

 In one operation, you can choose two different indices $i$ and $j$ ($1 \le i, j \le n$). If $gcd(a_i, a_j)$ is equal to the minimum element of the whole array $a$, you can swap $a_i$ and $a_j$. $gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.

 Now you'd like to make $a$ non-decreasing using the operation any number of times (possibly zero). Determine if you can do this.

 An array $a$ is non-decreasing if and only if $a_1 \le a_2 \le \ldots \le a_n$.


-----Input-----

 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

 The first line of each test case contains one integer $n$ ($1 \le n \le 10^5$) — the length of array $a$.

 The second line of each test case contains $n$ positive integers $a_1, a_2, \ldots a_n$ ($1 \le a_i \le 10^9$) — the array itself.

 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.


-----Output-----

 For each test case, output "YES" if it is possible to make the array $a$ non-decreasing using the described operation, or "NO" if it is impossible to do so.


-----Example-----
Input
4
1
8
6
4 3 6 6 2 9
4
4 5 6 7
5
7 5 2 2 4

Output
YES
YES
YES
NO



-----Note-----

 In the first and third sample, the array is already non-decreasing.

 In the second sample, we can swap $a_1$ and $a_3$ first, and swap $a_1$ and $a_5$ second to make the array non-decreasing.

 In the forth sample, we cannot the array non-decreasing using the operation.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Someone gave Alyona an array containing n positive integers a_1, a_2, ..., a_{n}. In one operation, Alyona can choose any element of the array and decrease it, i.e. replace with any positive integer that is smaller than the current one. Alyona can repeat this operation as many times as she wants. In particular, she may not apply any operation to the array at all.

Formally, after applying some operations Alyona will get an array of n positive integers b_1, b_2, ..., b_{n} such that 1 ≤ b_{i} ≤ a_{i} for every 1 ≤ i ≤ n. Your task is to determine the maximum possible value of mex of this array.

Mex of an array in this problem is the minimum positive integer that doesn't appear in this array. For example, mex of the array containing 1, 3 and 4 is equal to 2, while mex of the array containing 2, 3 and 2 is equal to 1.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the number of elements in the Alyona's array.

The second line of the input contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — the elements of the array.


-----Output-----

Print one positive integer — the maximum possible value of mex of the array after Alyona applies some (possibly none) operations.


-----Examples-----
Input
5
1 3 3 3 6

Output
5

Input
2
2 1

Output
3



-----Note-----

In the first sample case if one will decrease the second element value to 2 and the fifth element value to 4 then the mex value of resulting array 1 2 3 3 4 will be equal to 5.

To reach the answer to the second sample case one must not decrease any of the array elements.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:


Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an interactive problem. You should use flush operation after each printed line. For example, in C++ you should use fflush(stdout), in Java you should use System.out.flush(), and in Pascal — flush(output).

In this problem you should guess an array a which is unknown for you. The only information you have initially is the length n of the array a.

The only allowed action is to ask the sum of two elements by their indices. Formally, you can print two indices i and j (the indices should be distinct). Then your program should read the response: the single integer equals to ai + aj.

It is easy to prove that it is always possible to guess the array using at most n requests.

Write a program that will guess the array a by making at most n requests.

Interaction

In each test your program should guess a single array.

The input starts with a line containing integer n (3 ≤ n ≤ 5000) — the length of the array. Your program should read it at first.

After that your program should print to the standard output the requests about the sum of two elements or inform that the array is guessed.

  * In case your program is making a request to ask the sum of two elements, it should print line in the format "? i j" (i and j are distinct integers between 1 and n), where i and j are indices in the array a.
  * In case your program informs that the array is guessed, it should print line in the format "! a1 a2 ... an" (it is guaranteed that all ai are positive integers not exceeding 105), where ai is the i-th element of the array a. 



The response on a request is a single integer equal to ai + aj, printed on a separate line.

Your program can do at most n requests. Note that the final line «! a1 a2 ... an» is not counted as a request.

Do not forget about flush operation after each printed line.

After you program prints the guessed array, it should terminate normally.

Example

Input

5
 
9
 
7
 
9
 
11
 
6
 

Output

 
? 1 5
 
? 2 3
 
? 4 1
 
? 5 2
 
? 3 4
 
! 4 6 1 5 5

Note

The format of a test to make a hack is:

  * The first line contains an integer number n (3 ≤ n ≤ 5000) — the length of the array.
  * The second line contains n numbers a1, a2, ..., an (1 ≤ ai ≤ 105) — the elements of the array to guess. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a few weeks time, a new president will be elected in the country of Marecia. There are two political parties: the Constituents and the Federals. Each party has one presidential candidate; one of these will become the new president.

This year you are more involved than ever before: you are the candidate for the Constituents! With only a few weeks to go, you decide to take stock of the situation. Instead of touring blindly through the country, you feel that it is better to focus your attention on certain particular states.

The Marecian electoral system is quite complicated. Every registered voter will vote for exactly one of the two candidates, but the totals are not calculated nationwide. Instead, every state has a fixed number of delegates. After the popular vote is in, the delegates from all states travel by foot to the capital of Marecia, the city of Ashwington. One final round of voting is done in Ashwington: every delegate gets to vote for one of the two candidates. A delegate is required by law to vote for the candidate who received the majority of the votes in his own home state.

Your campaign team has painstakingly compiled a very accurate list of voting preferences per state. Therefore you now have the following information about every state:
 - The number of voters who will definitely vote for the Constituents;
 - The number of voters who will certainly vote for the Federals;
 - The number of voters who have not made up their minds yet.

Voters from the first two categories are not susceptible to any further campaigning, so your focus for the remaining weeks is on people of the third category. Specifically, you would like to know the minimum number of people you still have to convince in order to secure a victory.

If there is a tie on either state or national level, the law states that it is resolved in favour of the oldest of the two political parties, which unfortunately is the Federal party.

-----Input-----
The first line contains a single integer $S$, the number of states.

The following $S$ lines each contain four integers $D_ i$, $C_ i$, $F_ i$, $U_ i$, where
 - $D_ i$ denotes the number of delegates for the $i$-th state,
 - $C_ i$ denotes the number of registered voters in the $i$-th state who will definitely vote for the Constituents,
 - $F_ i$ denotes the number of registered voters in the $i$-th state who will certainly vote for the Federals,
 - $U_ i$ denotes the number of undecided voters in the $i$-th state.

There are at most $2016$ delegates in total, and the total number of registered voters is at most $10^9$. Every state has at least one delegate and at least one registered voter. There is at least one state.

-----Output-----
Output one line with a single integer: the minimum number of voters you have to convince to secure a victory. If it is not possible for you to win the election, output “impossible” instead.

-----Examples-----
Sample Input 1:
3
7 2401 3299 0
6 2401 2399 0
2 750 750 99
Sample Output 1:
50

Sample Input 2:
3
7 100 200 200
8 100 300 200
9 100 400 200
Sample Output 2:
impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Cybermen solved that first test much quicker than the Daleks. Luckily for us, the Daleks were angry (shocking!) and they destroyed some of the Cybermen.

After the fighting stopped, Heidi gave them another task to waste their time on.

There are $n$ points on a plane. Given a radius $r$, find the maximum number of points that can be covered by an $L^1$-ball with radius $r$.

An $L^1$-ball with radius $r$ and center $(x_0, y_0)$ in a 2D-plane is defined as the set of points $(x, y)$ such that the Manhattan distance between $(x_0, y_0)$ and $(x, y)$ is at most $r$.

Manhattan distance between $(x_0, y_0)$ and $(x, y)$ is defined as $|x - x_0| + |y - y_0|$.


-----Input-----

The first line contains two integers $n, r$ ($1 \le n \le 300\,000, 1 \le r \le 10^6$), the number of points and the radius of the ball, respectively. 

Each of the next $n$ lines contains integers $x_i, y_i$ ($-10^6 \leq x_i, y_i \leq 10^6$), describing the coordinates of the $i$-th point.

It is guaranteed, that all points are distinct.


-----Output-----

Print one integer — the maximum number points that an $L^1$-ball with radius $r$ can cover.


-----Examples-----
Input
5 1
1 1
1 -1
-1 1
-1 -1
2 0

Output
3

Input
5 2
1 1
1 -1
-1 1
-1 -1
2 0

Output
5



-----Note-----

In the first example, a ball centered at $(1, 0)$ covers the points $(1, 1)$, $(1, -1)$, $(2, 0)$.

In the second example, a ball centered at $(0, 0)$ covers all the points.

Note that $x_0$ and $y_0$ need not be integer.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are quite a lot of ways to have fun with inflatable balloons. For example, you can fill them with water and see what happens.

Grigory and Andrew have the same opinion. So, once upon a time, they went to the shop and bought $n$ packets with inflatable balloons, where $i$-th of them has exactly $a_i$ balloons inside.

They want to divide the balloons among themselves. In addition, there are several conditions to hold:
 -  Do not rip the packets (both Grigory and Andrew should get unbroken packets); -  Distribute all packets (every packet should be given to someone); -  Give both Grigory and Andrew at least one packet; -  To provide more fun, the total number of balloons in Grigory's packets should not be equal to the total number of balloons in Andrew's packets. 
Help them to divide the balloons or determine that it's impossible under these conditions.

Input Specification:
The first line of input contains a single integer $n$ ($1 \le n \le 10$) — the number of packets with balloons.

The second line contains $n$ integers: $a_1$, $a_2$, $\ldots$, $a_n$ ($1 \le a_i \le 1000$) — the number of balloons inside the corresponding packet.

Output Specification:
If it's impossible to divide the balloons satisfying the conditions above, print $-1$.

Otherwise, print an integer $k$ — the number of packets to give to Grigory followed by $k$ distinct integers from $1$ to $n$ — the indices of those. The order of packets doesn't matter.

If there are multiple ways to divide balloons, output any of them.

Demo Input:
['3\n1 2 1\n', '2\n5 5\n', '1\n10\n']

Demo Output:
['2\n1 2\n', '-1\n', '-1\n']

Note:
In the first test Grigory gets $3$ balloons in total while Andrey gets $1$.

In the second test there's only one way to divide the packets which leads to equal numbers of balloons.

In the third test one of the boys won't get a packet at all.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It seems that Borya is seriously sick. He is going visit n doctors to find out the exact diagnosis. Each of the doctors needs the information about all previous visits, so Borya has to visit them in the prescribed order (i.e. Borya should first visit doctor 1, then doctor 2, then doctor 3 and so on). Borya will get the information about his health from the last doctor.

Doctors have a strange working schedule. The doctor i goes to work on the s_{i}-th day and works every d_{i} day. So, he works on days s_{i}, s_{i} + d_{i}, s_{i} + 2d_{i}, ....

The doctor's appointment takes quite a long time, so Borya can not see more than one doctor per day. What is the minimum time he needs to visit all doctors?


-----Input-----

First line contains an integer n — number of doctors (1 ≤ n ≤ 1000). 

Next n lines contain two numbers s_{i} and d_{i} (1 ≤ s_{i}, d_{i} ≤ 1000).


-----Output-----

Output a single integer — the minimum day at which Borya can visit the last doctor.


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

Output
4

Input
2
10 1
6 5

Output
11



-----Note-----

In the first sample case, Borya can visit all doctors on days 2, 3 and 4.

In the second sample case, Borya can visit all doctors on days 10 and 11.

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