vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
# Task
 Your Informatics teacher at school likes coming up with new ways to help you understand the material. When you started studying numeral systems, he introduced his own numeral system, which he's convinced will help clarify things. His numeral system has base 26, and its digits are represented by English capital letters - `A for 0, B for 1, and so on`.

 The teacher assigned you the following numeral system exercise: given a one-digit `number`, you should find all unordered pairs of one-digit numbers whose values add up to the `number`.

# Example

 For `number = 'G'`, the output should be `["A + G", "B + F", "C + E", "D + D"]`

 Translating this into the decimal numeral system we get: number = 6, so it is `["0 + 6", "1 + 5", "2 + 4", "3 + 3"]`.

# Input/Output

 - `[input]` string(char in C#) `number`

   A character representing a correct one-digit number in the new numeral system.

   Constraints: `'A' ≤ number ≤ 'Z'.`

 - `[output]` a string array

   An array of strings in the format "letter1 + letter2", where "letter1" and "letter2" are correct one-digit numbers in the new numeral system. The strings should be sorted by "letter1".

   Note that "letter1 + letter2" and "letter2 + letter1" are equal pairs and we don't consider them to be different.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Mahmoud and Ehab and another array construction task

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Mahmoud has an array *a* consisting of *n* integers. He asked Ehab to find another array *b* of the same length such that:
 -  *b* is lexicographically greater than or equal to *a*. -  *b**i*<=≥<=2. -  *b* is pairwise coprime: for every 1<=≤<=*i*<=&lt;<=*j*<=≤<=*n*, *b**i* and *b**j* are coprime, i. e. *GCD*(*b**i*,<=*b**j*)<==<=1, where *GCD*(*w*,<=*z*) is the greatest common divisor of *w* and *z*. 
Ehab wants to choose a special array so he wants the lexicographically minimal array between all the variants. Can you find it?

An array *x* is lexicographically greater than an array *y* if there exists an index *i* such than *x**i*<=&gt;<=*y**i* and *x**j*<==<=*y**j* for all 1<=≤<=*j*<=&lt;<=*i*. An array *x* is equal to an array *y* if *x**i*<==<=*y**i* for all 1<=≤<=*i*<=≤<=*n*.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=105), the number of elements in *a* and *b*.

The second line contains *n* integers *a*1, *a*2, ..., *a**n* (2<=≤<=*a**i*<=≤<=105), the elements of *a*.

Output Specification:
Output *n* space-separated integers, the *i*-th of them representing *b**i*.

Demo Input:
['5\n2 3 5 4 13\n', '3\n10 3 7\n']

Demo Output:
['2 3 5 7 11 ', '10 3 7 ']

Note:
Note that in the second sample, the array is already pairwise coprime so we printed it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have N lamps numbered 1 to N, and N buttons numbered 1 to N. Initially, Lamp 1, 2, \cdots, A are on, and the other lamps are off.

Snuke and Ringo will play the following game.

* First, Ringo generates a permutation (p_1,p_2,\cdots,p_N) of (1,2,\cdots,N). The permutation is chosen from all N! possible permutations with equal probability, without being informed to Snuke.

* Then, Snuke does the following operation any number of times he likes:

* Choose a lamp that is on at the moment. (The operation cannot be done if there is no such lamp.) Let Lamp i be the chosen lamp. Press Button i, which switches the state of Lamp p_i. That is, Lamp p_i will be turned off if it is on, and vice versa.



At every moment, Snuke knows which lamps are on. Snuke wins if all the lamps are on, and he will surrender when it turns out that he cannot win. What is the probability of winning when Snuke plays optimally?

Let w be the probability of winning. Then, w \times N! will be an integer. Compute w \times N! modulo (10^9+7).

Constraints

* 2 \leq N \leq 10^7
* 1 \leq A \leq \min(N-1,5000)

Input

Input is given from Standard Input in the following format:


N A


Output

Print w \times N! modulo (10^9+7), where w is the probability of Snuke's winning.

Examples

Input

3 1


Output

2


Input

3 2


Output

3


Input

8 4


Output

16776


Input

9999999 4999


Output

90395416

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Žofka is bending a copper wire. She starts with a straight wire placed on the table with the starting point glued to the middle of the table. She then repeatedly picks a point on the wire and bends the part starting at that point (away from the starting point) by $90$ degrees (either clockwise or counterclockwise). Throughout the process the starting point stays glued to the middle of the table.

The most important consideration is that she does not want the wire to touch itself as she bends it (that would summon the wire ghost). She needs your help. She has a list of points together with the direction at each point (clockwise or counterclockwise). She wants to know if bending the wire at the listed points in the given order would cause the wire ghost to appear at any time during the process.

-----Input-----
The first line contains two integers $L$ and $n$ where $L$ is the length of the wire and $n$ is the number of points. Each of the next $n$ lines contains a number from $\{ 0,\dots ,L\} $ (describing the point on the wire) followed by W (clockwise) or C (counter clockwise). You may assume $L\leq 100000000$ and $n\leq 1000$.

-----Output-----
The output consists of a single line consisting of the string GHOST if the wire would touch itself during the bending, and the string SAFE otherwise.

-----Examples-----
Sample Input:
4 3
3 C
2 C
1 C
Sample Output:
GHOST

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob are decorating a Christmas Tree. 

Alice wants only $3$ types of ornaments to be used on the Christmas Tree: yellow, blue and red. They have $y$ yellow ornaments, $b$ blue ornaments and $r$ red ornaments.

In Bob's opinion, a Christmas Tree will be beautiful if:  the number of blue ornaments used is greater by exactly $1$ than the number of yellow ornaments, and  the number of red ornaments used is greater by exactly $1$ than the number of blue ornaments. 

That is, if they have $8$ yellow ornaments, $13$ blue ornaments and $9$ red ornaments, we can choose $4$ yellow, $5$ blue and $6$ red ornaments ($5=4+1$ and $6=5+1$).

Alice wants to choose as many ornaments as possible, but she also wants the Christmas Tree to be beautiful according to Bob's opinion.

In the example two paragraphs above, we would choose $7$ yellow, $8$ blue and $9$ red ornaments. If we do it, we will use $7+8+9=24$ ornaments. That is the maximum number.

Since Alice and Bob are busy with preparing food to the New Year's Eve, they are asking you to find out the maximum number of ornaments that can be used in their beautiful Christmas Tree! 

It is guaranteed that it is possible to choose at least $6$ ($1+2+3=6$) ornaments.


-----Input-----

The only line contains three integers $y$, $b$, $r$ ($1 \leq y \leq 100$, $2 \leq b \leq 100$, $3 \leq r \leq 100$) — the number of yellow, blue and red ornaments. 

It is guaranteed that it is possible to choose at least $6$ ($1+2+3=6$) ornaments.


-----Output-----

Print one number — the maximum number of ornaments that can be used. 


-----Examples-----
Input
8 13 9

Output
24
Input
13 3 6

Output
9


-----Note-----

In the first example, the answer is $7+8+9=24$.

In the second example, the answer is $2+3+4=9$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A group of rebels travelling on a square hoverboard is ambushed by Imperial Stormtroopers.Their big hoverboard is an easy target, so they decide to split the board into smaller square hoverboards so that they can bolt away easily.But they should also make sure they don't get too spread out.Help the rebels split the craft into minimum number of smaller crafts possible.

-----Input-----
A single integer N denoting the side length of the big hoverboard.

-----Output-----
In the first line, output the integer 'k' which is the minimum number of square boards into which the bigger board can be split up.

In the second line, output k space separated integers which denote the sizes of the smaller square hoverboards.This must be in increasing order of sizes.

-----Constraints-----
N ranges from 2 to 50.

-----Example-----
Input:
3

Output:
6
1 1 1 1 1 2

-----Explanation-----
A square of side length 3 can be split into smaller squares in two ways: Either into 9 squares of side1 or 5 squares of side 1 and 1 square of size 2.The second case is the favourable one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a convex polygon with $N$ vertices, with the additional property that no three diagonals intersect in a single point. Find the number of intersections between pairs of diagonals in such a polygon.

The figure below shows one such polygon with 6 vertices.

Note that a polygon is convex if all of its interior angles are less than 180 degrees.

-----Input-----
The first and only line of input contains a single integer $N, 3\leq N\leq 100$ denoting the number of vertices.

-----Output-----
Output the number of intersections on a single line.

-----Examples-----
Sample Input 1:
3
Sample Output 1:
0

Sample Input 2:
4
Sample Output 2:
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Summer in Texas can be very hot. But Texans are tough, and in a weird way some of them enjoy the heat; for even the heat is bigger in Texas. But the heat can be quite uncomfortable for computer science students who are new to Texas and are not used to the sweating it can cause.

These students want to minimize the amount they sweat while walking from their dormitory to class. When they enter the sunshine, they begin sweating at the rate $r_0$ gallons/hour (where $r_0 > 0$). The longer they stay in the sun, the more they sweat. They sweat at a rate proportional to the square of how long they have been continuously exposed to the sun. Put another way, if they are exposed to the sun for twice as long, they sweat four times as much. But if they find a shady spot along the way, their continuous sun exposure is broken and they stop sweating immediately. They can then sit in the shade and cool off completely before continuing on their journey to class. Of course, leaving the shade means they begin sweating again, but starting at the lower rate $r_0$ (since they have cooled off).

Write a program that helps a student find a path from the dormitory to class which minimizes the total amount of sweat she expends.

-----Input-----
Input describes the locations of shady spots on campus as well as the student’s dormitory and class locations. Input begins with a line containing an integer $0 \leq n \leq 2500$, the number of shady spots. Each of the next $n$ lines contains a pair of integers $x~ y$ specifying the coordinates of a shady spot. No two shady spots have the same coordinates. Following the shady spots are two more lines in the same format which specify the coordinates of the student’s dormitory and class, respectively.

-----Output-----
Print a path the student can take to get from her dormitory to class. The path should minimize the total sweat produced along the whole path. Print the path as indexes of the shady spots (from the order given in the input, with the first shady spot having index 0). If the best path contains no shady spots, output a single ‘-’. If there are multiple paths that minimize the total sweat, print any one of them.

-----Examples-----
Sample Input 1:
3
1 1
2 -2
5 -1
0 0
9 0
Sample Output 1:
1
2

Sample Input 2:
6
8 2
4 0
8 0
4 -1
7 -1
6 -2
2 1
9 2
Sample Output 2:
1
3
5
4
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Organising a group trip for the elderly can be a daunting task... Not least because of the fussy participants, each of whom will only make the trip on condition that some other participant also comes.

After some effort, you have taken from each of your participants a number, indicating that this participant will refuse to join the excursion unless the participant with that number also joins– the less choosy simply give their own number. This would be easy enough to resolve (just send all of them) but the bus you are going to use during the trip has only a fixed number of places.

-----Task-----
Given the preferences of all participants, find the maximum number of participants that can join.

-----Input-----
The first line of input contains two integers $n$ and $k$ ($1 \leq k \leq n \leq 1000$), where $n$ denotes the total number of participants and $k$ denotes the number of places on the bus.

The second line contains $n$ integers $x_{i}$ for $i=1,2,\ldots ,n$, where $1 \leq x_ i \leq n$. The meaning of $x_ i$ is that the $i$-th participant will refuse to join the excursion unless the $x_ i$-th participant also joins.

-----Output-----
Output one integer: the maximum number of participants that can join the excursion, so that all the participants’ preferences are obeyed and the capacity of the bus is not exceeded.

-----Examples-----
Sample Input 1:
4 4
1 2 3 4
Sample Output 1:
4

Sample Input 2:
12 3
2 3 4 5 6 7 4 7 8 8 12 12
Sample Output 2:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an IP address, remove leading zeros from the IP address. Note that our IP address here can be a little different. It can have numbers greater than 255. Also, it does not necessarily have 4 numbers. The count can be lesser/more.
Example 1:
Input:
S = "100.020.003.400"
Output: 100.20.3.400
Explanation: The leading zeros are removed
from 20 and 3.
Example 2:
Input: 
S = "100.000.010.0999"
Output: 100.0.10.999
Explanation: The leading zeros are removed
from 0, 10 and 999.
Your Task:
You don't need to read input or print anything. Your task is to complete the function newIPAdd() which takes the string S representing the IP address as input and returns a string representing the resultant IP address. 
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(|S|).
Constraints:
1<=|S|<=1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mishka has got n empty boxes. For every i (1 ≤ i ≤ n), i-th box is a cube with side length a_{i}.

Mishka can put a box i into another box j if the following conditions are met:

  i-th box is not put into another box;  j-th box doesn't contain any other boxes;  box i is smaller than box j (a_{i} < a_{j}). 

Mishka can put boxes into each other an arbitrary number of times. He wants to minimize the number of visible boxes. A box is called visible iff it is not put into some another box.

Help Mishka to determine the minimum possible number of visible boxes!


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 5000) — the number of boxes Mishka has got.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where a_{i} is the side length of i-th box.


-----Output-----

Print the minimum possible number of visible boxes.


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

Output
1

Input
4
4 2 4 3

Output
2



-----Note-----

In the first example it is possible to put box 1 into box 2, and 2 into 3.

In the second example Mishka can put box 2 into box 3, and box 4 into box 1.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Gerald is setting the New Year table. The table has the form of a circle; its radius equals *R*. Gerald invited many guests and is concerned whether the table has enough space for plates for all those guests. Consider all plates to be round and have the same radii that equal *r*. Each plate must be completely inside the table and must touch the edge of the table. Of course, the plates must not intersect, but they can touch each other. Help Gerald determine whether the table is large enough for *n* plates.

Input Specification:
The first line contains three integers *n*, *R* and *r* (1<=≤<=*n*<=≤<=100, 1<=≤<=*r*,<=*R*<=≤<=1000) — the number of plates, the radius of the table and the plates' radius.

Output Specification:
Print "YES" (without the quotes) if it is possible to place *n* plates on the table by the rules given above. If it is impossible, print "NO".

Remember, that each plate must touch the edge of the table.

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

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

Note:
The possible arrangement of the plates for the first sample is:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In Homer's country, there are n cities numbered 1 to n and they form a tree. That is, there are (n-1) undirected roads between these n cities and every two cities can reach each other through these roads. 

Homer's country is an industrial country, and each of the n cities in it contains some mineral resource. The mineral resource of city i is labeled a_i. 

Homer is given the plans of the country in the following q years. The plan of the i-th year is described by four parameters u_i, v_i, l_i and r_i, and he is asked to find any mineral resource c_i such that the following two conditions hold: 

  * mineral resource c_i appears an odd number of times between city u_i and city v_i; and 
  * l_i ≤ c_i ≤ r_i. 



As the best friend of Homer, he asks you for help. For every plan, find any such mineral resource c_i, or tell him that there doesn't exist one.

Input

The first line contains two integers n (1 ≤ n ≤ 3 ⋅ 10^5) and q (1 ≤ q ≤ 3 ⋅ 10^5), indicating the number of cities and the number of plans.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n).

Then the i-th line of the following (n-1) lines contains two integers x_i and y_i (1 ≤ x_i, y_i ≤ n) with x_i ≠ y_i, indicating that there is a bidirectional road between city x_i and city y_i. It is guaranteed that the given roads form a tree.

Then the i-th line of the following q lines contains four integers u_i, v_i, l_i, r_i (1 ≤ u_i ≤ n, 1 ≤ v_i ≤ n, 1 ≤ l_i ≤ r_i ≤ n), indicating the plan of the i-th year.

Output

Print q lines, the i-th of which contains an integer c_i such that 

  * c_i = {-1} if there is no such mineral resource that meets the required condition; or 
  * c_i is the label of the chosen mineral resource of the i-th year. The chosen mineral resource c_i should meet those conditions in the i-th year described above in the problem statement. If there are multiple choices of c_i, you can print any of them. 

Example

Input


6 8
3 2 1 3 1 3
1 2
1 3
2 4
2 5
4 6
3 5 1 1
3 5 1 3
3 5 1 3
1 1 2 2
1 1 3 3
1 4 1 5
1 6 1 3
1 6 1 3


Output


-1
2
3
-1
3
2
2
3

Note

In the first three queries, there are four cities between city 3 and city 5, which are city 1, city 2, city 3 and city 5. The mineral resources appear in them are mineral resources 1 (appears in city 3 and city 5), 2 (appears in city 2) and 3 (appears in city 1). It is noted that 

  * The first query is only to check whether mineral source 1 appears an odd number of times between city 3 and city 5. The answer is no, because mineral source 1 appears twice (an even number of times) between city 3 and city 5. 
  * The second and the third queries are the same but they can choose different mineral resources. Both mineral resources 2 and 3 are available. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have an array A of non-negative integers.
For every (contiguous) subarray B = [A[i], A[i+1], ..., A[j]] (with i <= j), we take the bitwise OR of all the elements in B, obtaining a result A[i] | A[i+1] | ... | A[j].
Return the number of possible results.  (Results that occur more than once are only counted once in the final answer.)
 

Example 1:
Input: [0]
Output: 1
Explanation: 
There is only one possible result: 0.


Example 2:
Input: [1,1,2]
Output: 3
Explanation: 
The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.


Example 3:
Input: [1,2,4]
Output: 6
Explanation: 
The possible results are 1, 2, 3, 4, 6, and 7.




 
Note:

1 <= A.length <= 50000
0 <= A[i] <= 10^9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Inspired by the development team at Vooza, write the function `howManyLightsabersDoYouOwn`/`how_many_light_sabers_do_you_own` that 

* accepts the name of a programmer, and
* returns the number of lightsabers owned by that person.

The only person who owns lightsabers is Zach, by the way. He owns 18, which is an awesome number of lightsabers. Anyone else owns 0.

```if:coffeescript,javascript,php,python,ruby,typescript
**Note**: your function should have a default parameter.
```

```c#
Kata.HowManyLightsabersDoYouOwn("Adam") == 0
Kata.HowManyLightsabersDoYouOwn("Zach") == 18
```
```python
how_many_light_sabers_do_you_own('Zach') == 18
how_many_light_sabers_do_you_own('Adam') == 0
how_many_light_sabers_do_you_own()       == 0
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this problem you will write a simple generator of Brainfuck (https://en.wikipedia.org/wiki/Brainfuck) calculators.

You are given an arithmetic expression consisting of integers from 0 to 255 and addition/subtraction signs between them. Output a Brainfuck program which, when executed, will print the result of evaluating this expression.

We use a fairly standard Brainfuck interpreter for checking the programs:



 30000 memory cells.

 memory cells store integers from 0 to 255 with unsigned 8-bit wraparound.

 console input (, command) is not supported, but it's not needed for this problem.


-----Input-----

The only line of input data contains the arithmetic expression. The expression will contain between 2 and 10 operands, separated with arithmetic signs plus and/or minus. Each operand will be an integer between 0 and 255, inclusive. The calculations result is guaranteed to be an integer between 0 and 255, inclusive (results of intermediary calculations might be outside of these boundaries).


-----Output-----

Output a Brainfuck program which, when executed, will print the result of evaluating this expression. The program must be at most 5000000 characters long (including the non-command characters), and its execution must be complete in at most 50000000 steps.


-----Examples-----
Input
2+3

Output
++>
+++>
<[<+>-]<
++++++++++++++++++++++++++++++++++++++++++++++++.

Input
9-7

Output
+++++++++>
+++++++>
<[<->-]<
++++++++++++++++++++++++++++++++++++++++++++++++.



-----Note-----

You can download the source code of the Brainfuck interpreter by the link http://assets.codeforces.com/rounds/784/bf.cpp. We use this code to interpret outputs.

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