vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given a non-negative number N in the form of string. The task is to apply at most one swap operation on the number N so that the result is just a previous possible number.
Note:  Leading zeros are not allowed.
 
Example 1:
Input :
S = "12435"
Output: 
12345
Explanation:
Although the number 12354 
will be the largest smaller 
number from 12435. But it is 
not possible to make it using 
only one swap. So swap 
4 and 3 and get 12345.
 
Example 2:
Input: 
S = " 12345"
Output: 
-1
Explanation:
Digits are in increasing order. 
So it is not possible to 
make a smaller number from it.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function previousNumber() which takes the string S and returns the previous number of S. If no such number exists return -1;
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
2<=|Number length |<=10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let w be a string consisting of lowercase letters.
We will call w beautiful if the following condition is satisfied:
 - Each lowercase letter of the English alphabet occurs even number of times in w.
You are given the string w. Determine if w is beautiful.

-----Constraints-----
 - 1 \leq |w| \leq 100
 - w consists of lowercase letters (a-z).

-----Input-----
The input is given from Standard Input in the following format:
w

-----Output-----
Print Yes if w is beautiful. Print No otherwise.

-----Sample Input-----
abaccaba

-----Sample Output-----
Yes

a occurs four times, b occurs twice, c occurs twice and the other letters occur zero times.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Once Bob decided to lay a parquet floor in his living room. The living room is of size *n*<=×<=*m* metres. Bob had planks of three types: *a* planks 1<=×<=2 meters, *b* planks 2<=×<=1 meters, and *c* planks 2<=×<=2 meters. Help Bob find out, if it is possible to parquet the living room with such a set of planks, and if it is possible, find one of the possible ways to do so. Bob doesn't have to use all the planks.

Input Specification:
The first input line contains 5 space-separated integer numbers *n*, *m*, *a*, *b*, *c* (1<=≤<=*n*,<=*m*<=≤<=100,<=0<=≤<=*a*,<=*b*,<=*c*<=≤<=104), *n* and *m* — the living room dimensions, *a*, *b* and *c* — amount of planks 1<=×<=2, 2<=×<=1 и 2<=×<=2 respectively. It's not allowed to turn the planks.

Output Specification:
If it is not possible to parquet the room with such a set of planks, output IMPOSSIBLE. Otherwise output one of the possible ways to parquet the room — output *n* lines with *m* lower-case Latin letters each. Two squares with common sides should contain the same letters, if they belong to one and the same plank, and different letters otherwise. Different planks can be marked with one and the same letter (see examples). If the answer is not unique, output any.

Demo Input:
['2 6 2 2 1\n', '1 1 100 100 100\n', '4 4 10 10 10\n']

Demo Output:
['aabcca\naabdda\n', 'IMPOSSIBLE\n', 'aabb\naabb\nbbaa\nbbaa\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given string s and an integer, you have to transform s into a palindrome. In order to achieve that you have to perform exactly k insertion of characters(you cannot perform anymore or less number of insertions). The task is to check if the string can be converted to a palindrome by making exactly k insertions.
Example 1:
Input: s = "abac", K = 2
Output: 1
Explanation: "abac" can be transformed to 
"cabbac" (which is palindrome) adding 
two characters c and b.
Example 2:
Input: s = "abcde", K = 3
Output: 0
Explanation: "abcde" cannot be transformed
to palindrome using 3 insertions.
Your Task:  
You don't need to read input or print anything. Complete the function isPossiblePalindrome() which takes s and K as input parameters and returns a boolean value
Expected Time Complexity: O(|s|^{2})
Expected Auxiliary Space: O(|s|^{2})
Constraints:
1 ≤ |s| ≤ 103
s contains lower case English alphabets

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two non-negative decimal integers $a$ and $b$, calculate their AND (logical conjunction), OR (logical disjunction) and XOR (exclusive disjunction) and print them in binary representation of 32 bits.

Constraints

* $0 \leq a, b \leq 2^{32} - 1$

Input

The input is given in the following format.


$a \; b$


Output

Print results of AND, OR and XOR in a line respectively.

Example

Input

8 10


Output

00000000000000000000000000001000
00000000000000000000000000001010
00000000000000000000000000000010

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
My friend wants a new band name for her band. She like bands that use the formula: "The" + a noun with the first letter capitalized, for example:

`"dolphin" -> "The Dolphin"`

However, when a noun STARTS and ENDS with the same letter, she likes to repeat the noun twice and connect them together with the first and last letter, combined into one word (WITHOUT "The" in front), like this:

`"alaska" -> "Alaskalaska"`

Complete the function that takes a noun as a string, and returns her preferred band name written as a string.

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

You have to write a function `pattern` which creates the following pattern (See Examples) upto desired number of rows.

If the Argument is `0` or a Negative Integer then it should return `""` i.e. empty string.

### Examples:

`pattern(9)`:

    123456789
    234567891
    345678912
    456789123
    567891234
    678912345
    789123456
    891234567
    912345678

`pattern(5)`:

    12345
    23451
    34512
    45123
    51234

Note: There are no spaces in the pattern

Hint: Use `\n` in string to jump to next line

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Limak is a little polar bear. He likes nice strings — strings of length n, consisting of lowercase English letters only.

The distance between two letters is defined as the difference between their positions in the alphabet. For example, $\operatorname{dist}(c, e) = \operatorname{dist}(e, c) = 2$, and $\operatorname{dist}(a, z) = \operatorname{dist}(z, a) = 25$.

Also, the distance between two nice strings is defined as the sum of distances of corresponding letters. For example, $\operatorname{dist}(a f, d b) = \operatorname{dist}(a, d) + \operatorname{dist}(f, b) = 3 + 4 = 7$, and $\text{dist(bear, roar)} = 16 + 10 + 0 + 0 = 26$.

Limak gives you a nice string s and an integer k. He challenges you to find any nice string s' that $\operatorname{dist}(s, s^{\prime}) = k$. Find any s' satisfying the given conditions, or print "-1" if it's impossible to do so.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use gets/scanf/printf instead of getline/cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 10^5, 0 ≤ k ≤ 10^6).

The second line contains a string s of length n, consisting of lowercase English letters.


-----Output-----

If there is no string satisfying the given conditions then print "-1" (without the quotes).

Otherwise, print any nice string s' that $\operatorname{dist}(s, s^{\prime}) = k$.


-----Examples-----
Input
4 26
bear

Output
roar
Input
2 7
af

Output
db

Input
3 1000
hey

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day during the fight between good and evil, Meganath used his  Brahmastra on Lakshman. As nothing could stop a  Brahmastra so Lakshman got badly injured and would die the next day. Sushen, the doctor, was called to cure Lakshman. Sushen explained following thing.

He said "  Brahmastra consists of an array of integers and to find an antidote for it you have to find the sum of number of square free divisors of each number in the array ". Formally you will be given an array A of positive integers and for  each element A[i] find it's number of square free divisors, d[i]. Finally you have to compute the sum of all d[i]'s.

Input:

On the first line there will be N, denoting the number of integers in the array.

On the next line there will be N positive integers, A[i].

Output:

Output consist of one line denoting the value of the required sum.

Constraint:

0 < N ≤2000000 (2*10^6)

0 < A[i] ≤ 10000000 (10^7)

Note: Use scanf() , printf() for I/O

SAMPLE INPUT
4
8 8 8 8

SAMPLE OUTPUT
8

Explanation

Number of square free divisors of  8 are 2 {1, 2}.

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

Time Limit: 2 seconds

Memory Limit: 64 megabytes

Problem Description:
Nick is interested in prime numbers. Once he read about Goldbach problem. It states that every even integer greater than 2 can be expressed as the sum of two primes. That got Nick's attention and he decided to invent a problem of his own and call it Noldbach problem. Since Nick is interested only in prime numbers, Noldbach problem states that at least *k* prime numbers from 2 to *n* inclusively can be expressed as the sum of three integer numbers: two neighboring prime numbers and 1. For example, 19 = 7 + 11 + 1, or 13 = 5 + 7 + 1.

Two prime numbers are called neighboring if there are no other prime numbers between them.

You are to help Nick, and find out if he is right or wrong.

Input Specification:
The first line of the input contains two integers *n* (2<=≤<=*n*<=≤<=1000) and *k* (0<=≤<=*k*<=≤<=1000).

Output Specification:
Output YES if at least *k* prime numbers from 2 to *n* inclusively can be expressed as it was described above. Otherwise output NO.

Demo Input:
['27 2\n', '45 7\n']

Demo Output:
['YES', 'NO']

Note:
In the first sample the answer is YES since at least two numbers can be expressed as it was described (for example, 13 and 19). In the second sample the answer is NO since it is impossible to express 7 prime numbers from 2 to 45 in the desired form.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Susie, thanks to her older brother, likes to play with cars. Today she decided to set up a tournament between them. The process of a tournament is described in the next paragraph.

There are n toy cars. Each pair collides. The result of a collision can be one of the following: no car turned over, one car turned over, both cars turned over. A car is good if it turned over in no collision. The results of the collisions are determined by an n × n matrix А: there is a number on the intersection of the і-th row and j-th column that describes the result of the collision of the і-th and the j-th car:    - 1: if this pair of cars never collided.  - 1 occurs only on the main diagonal of the matrix.  0: if no car turned over during the collision.  1: if only the i-th car turned over during the collision.  2: if only the j-th car turned over during the collision.  3: if both cars turned over during the collision. 

Susie wants to find all the good cars. She quickly determined which cars are good. Can you cope with the task?


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100) — the number of cars.

Each of the next n lines contains n space-separated integers that determine matrix A. 

It is guaranteed that on the main diagonal there are  - 1, and  - 1 doesn't appear anywhere else in the matrix.

It is guaranteed that the input is correct, that is, if A_{ij} = 1, then A_{ji} = 2, if A_{ij} = 3, then A_{ji} = 3, and if A_{ij} = 0, then A_{ji} = 0.


-----Output-----

Print the number of good cars and in the next line print their space-separated indices in the increasing order.


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

Output
2
1 3 
Input
4
-1 3 3 3
3 -1 3 3
3 3 -1 3
3 3 3 -1

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an alphabet consisting of n letters, your task is to make a string of the maximum possible length so that the following conditions are satisfied:   the i-th letter occurs in the string no more than a_{i} times;  the number of occurrences of each letter in the string must be distinct for all the letters that occurred in the string at least once. 


-----Input-----

The first line of the input contains a single integer n (2  ≤  n  ≤  26) — the number of letters in the alphabet.

The next line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^9) — i-th of these integers gives the limitation on the number of occurrences of the i-th character in the string.


-----Output-----

Print a single integer — the maximum length of the string that meets all the requirements.


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

Output
11

Input
3
1 1 2

Output
3



-----Note-----

For convenience let's consider an alphabet consisting of three letters: "a", "b", "c". In the first sample, some of the optimal strings are: "cccaabbccbb", "aabcbcbcbcb". In the second sample some of the optimal strings are: "acc", "cbc".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ emotes in very popular digital collectible card game (the game is pretty famous so we won't say its name). The $i$-th emote increases the opponent's happiness by $a_i$ units (we all know that emotes in this game are used to make opponents happy).

You have time to use some emotes only $m$ times. You are allowed to use any emotion once, more than once, or not use it at all. The only restriction is that you cannot use the same emote more than $k$ times in a row (otherwise the opponent will think that you're trolling him).

Note that two emotes $i$ and $j$ ($i \ne j$) such that $a_i = a_j$ are considered different.

You have to make your opponent as happy as possible. Find the maximum possible opponent's happiness.


-----Input-----

The first line of the input contains three integers $n, m$ and $k$ ($2 \le n \le 2 \cdot 10^5$, $1 \le k \le m \le 2 \cdot 10^9$) — the number of emotes, the number of times you can use emotes and the maximum number of times you may use the same emote in a row.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is value of the happiness of the $i$-th emote.


-----Output-----

Print one integer — the maximum opponent's happiness if you use emotes in a way satisfying the problem statement.


-----Examples-----
Input
6 9 2
1 3 3 7 4 2

Output
54

Input
3 1000000000 1
1000000000 987654321 1000000000

Output
1000000000000000000



-----Note-----

In the first example you may use emotes in the following sequence: $4, 4, 5, 4, 4, 5, 4, 4, 5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Johnny are playing a simple guessing game. Johnny picks an arbitrary positive integer n (1<=n<=109) and gives Alice exactly k hints about the value of n. It is Alice's task to guess n, based on the received hints. 

Alice often has a serious problem guessing the value of n, and she's beginning to suspect that Johnny occasionally cheats, that is, gives her incorrect hints. 
After the last game, they had the following little conversation:

- [Alice] Johnny, you keep cheating!

- [Johnny] Indeed? You cannot prove it.

- [Alice] Oh yes I can. In fact, I can tell you with the utmost certainty that in the last game you lied to me at least *** times.

So, how many times at least did Johnny lie to Alice? Try to determine this, knowing only the hints Johnny gave to Alice.

-----Input-----
The first line of input contains t, the number of test cases (about 20). Exactly t test cases follow. 

Each test case starts with a line containing a single integer k, denoting the number of hints given by Johnny (1<=k<=100000). Each of the next k lines contains exactly one hint. The i-th hint is of the form:
operator li logical_value
where operator denotes one of the symbols < , > , or =; li is an integer (1<=li<=109), while logical_value is one of the words: Yes or No. The hint is considered correct if logical_value is the correct reply to the question: "Does the relation: n operator li hold?", and is considered to be false (a lie) otherwise.

-----Output-----
For each test case output a line containing a single integer, equal to the minimal possible number of Johnny's lies during the game.

-----Example-----
Input:
3
2
< 100 No
> 100 No
3
< 2 Yes
> 4 Yes
= 3 No
6
< 2 Yes
> 1 Yes
= 1 Yes
= 1 Yes
> 1 Yes
= 1 Yes

Output:
0
1
2

Explanation: for the respective test cases, the number picked by Johnny could have been e.g. n=100, n=5, and n=1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Andrew recently bought a new motorbike and wants to try it out on the roads of TreeLand.As the name suggests, Treeland is in the shape of a Tree , i.e , it is an undirected acyclic graph. Treeland has n junctions connected by n-1 roads. It is guaranteed that treeland is connected , i.e , any two junctions are reachable from each other. Andrew is at junction number 1. Andrew wants to ride his bike on a valid path from junction number 1 to another junction (he may even come back to junction number 1).A valid path is one which visits any given junction atmost 2 times.  

There is another constraint for the movement of Andrew on his bike . Let us root the tree at node number 1 . Let d(u) be the distance of u from node number 1 . Andrew is said to be going down if he moves from an ancestor of u to u directly . Similarly Andrew is said to be going up if he moves from u to an ancestor of u directly .  

Initially when Andrew is at node 1 he moves in the downward direction . Later he may change his direction to upward . However he cannot change it back to downward , i.e , on a valid path Andrew's direction can change atmost once .     

For all v from 1 to n , tell Andrew the number of valid paths from junction numbered 1 to junction numbered v.  

Note that a path must involve Andrew crossing non zero number of edges . Thus , a path beginning at junction number 1 and ending at junction number 1 , cannot be only the vertex 1 . It must visit some another node and then return back to 1.  

Input
The first line contains a number n denoting the number of junctions.
The next n-1 lines contain a pair of integers u v denoting there is a road between junction numbered u and junction numbered v.  

Output
Print n space separated integers where the v^th integer denotes the number of valid paths from junction numbered 1 to junction numbered v.    

Constraints
1 ≤ n ≤ 10^5
1 ≤ u,v ≤ n
There are no self-loops or multiple edges and it is guaranteed that the tree is connected.  

Note: A road between u and v means one can travel from u to v and vice versa.  

SAMPLE INPUT
6
1 4
4 2
3 4
4 5
5 6

SAMPLE OUTPUT
5 1 1 5 2 1

Explanation

For v=4,the paths are {1,4} , {1,4,3,4} , {1,4,2,4} , {1,4,5,4}  and {1,4,5,6,5,4}.
Note for v=1 the path {1} is not counted.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a tree consisting of n nodes. You want to write some labels on the tree's edges such that the following conditions hold:

  * Every label is an integer between 0 and n-2 inclusive. 
  * All the written labels are distinct. 
  * The largest value among MEX(u,v) over all pairs of nodes (u,v) is as small as possible. 



Here, MEX(u,v) denotes the smallest non-negative integer that isn't written on any edge on the unique simple path from node u to node v.

Input

The first line contains the integer n (2 ≤ n ≤ 10^5) — the number of nodes in the tree.

Each of the next n-1 lines contains two space-separated integers u and v (1 ≤ u,v ≤ n) that mean there's an edge between nodes u and v. It's guaranteed that the given graph is a tree.

Output

Output n-1 integers. The i^{th} of them will be the number written on the i^{th} edge (in the input order).

Examples

Input


3
1 2
1 3


Output


0
1


Input


6
1 2
1 3
2 4
2 5
5 6


Output


0
3
2
4
1

Note

The tree from the second sample:

<image>

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Caisa solved the problem with the sugar and now he is on the way back to home. 

Caisa is playing a mobile game during his path. There are (*n*<=+<=1) pylons numbered from 0 to *n* in this game. The pylon with number 0 has zero height, the pylon with number *i* (*i*<=&gt;<=0) has height *h**i*. The goal of the game is to reach *n*-th pylon, and the only move the player can do is to jump from the current pylon (let's denote its number as *k*) to the next one (its number will be *k*<=+<=1). When the player have made such a move, its energy increases by *h**k*<=-<=*h**k*<=+<=1 (if this value is negative the player loses energy). The player must have non-negative amount of energy at any moment of the time. 

Initially Caisa stand at 0 pylon and has 0 energy. The game provides a special opportunity: one can pay a single dollar and increase the height of anyone pylon by one. Caisa may use that opportunity several times, but he doesn't want to spend too much money. What is the minimal amount of money he must paid to reach the goal of the game?

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=105). The next line contains *n* integers *h*1, *h*2,<=..., *h**n* (1<=<=≤<=<=*h**i*<=<=≤<=<=105) representing the heights of the pylons.

Output Specification:
Print a single number representing the minimum number of dollars paid by Caisa.

Demo Input:
['5\n3 4 3 2 4\n', '3\n4 4 4\n']

Demo Output:
['4\n', '4\n']

Note:
In the first sample he can pay 4 dollars and increase the height of pylon with number 0 by 4 units. Then he can safely pass to the last pylon.

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