vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: On Corruption and Numbers

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Alexey, a merry Berland entrant, got sick of the gray reality and he zealously wants to go to university. There are a lot of universities nowadays, so Alexey is getting lost in the diversity — he has not yet decided what profession he wants to get. At school, he had bad grades in all subjects, and it's only thanks to wealthy parents that he was able to obtain the graduation certificate.

The situation is complicated by the fact that each high education institution has the determined amount of voluntary donations, paid by the new students for admission — *n**i* berubleys. He cannot pay more than *n**i*, because then the difference between the paid amount and *n**i* can be regarded as a bribe!

Each rector is wearing the distinctive uniform of his university. Therefore, the uniform's pockets cannot contain coins of denomination more than *r**i*. The rector also does not carry coins of denomination less than *l**i* in his pocket — because if everyone pays him with so small coins, they gather a lot of weight and the pocket tears. Therefore, a donation can be paid only by coins of denomination *x* berubleys, where *l**i*<=≤<=*x*<=≤<=*r**i* (Berland uses coins of any positive integer denomination). Alexey can use the coins of different denominations and he can use the coins of the same denomination any number of times. When Alexey was first confronted with such orders, he was puzzled because it turned out that not all universities can accept him! Alexey is very afraid of going into the army (even though he had long wanted to get the green uniform, but his dad says that the army bullies will beat his son and he cannot pay to ensure the boy's safety). So, Alexey wants to know for sure which universities he can enter so that he could quickly choose his alma mater.

Thanks to the parents, Alexey is not limited in money and we can assume that he has an unlimited number of coins of each type.

In other words, you are given *t* requests, each of them contains numbers *n**i*,<=*l**i*,<=*r**i*. For each query you need to answer, whether it is possible to gather the sum of exactly *n**i* berubleys using only coins with an integer denomination from *l**i* to *r**i* berubleys. You can use coins of different denominations. Coins of each denomination can be used any number of times.

Input Specification:
The first line contains the number of universities *t*, (1<=≤<=*t*<=≤<=1000) Each of the next *t* lines contain three space-separated integers: *n**i*,<=*l**i*,<=*r**i* (1<=≤<=*n**i*,<=*l**i*,<=*r**i*<=≤<=109; *l**i*<=≤<=*r**i*).

Output Specification:
For each query print on a single line: either "Yes", if Alexey can enter the university, or "No" otherwise.

Demo Input:
['2\n5 2 3\n6 4 5\n']

Demo Output:
['Yes\nNo\n']

Note:
You can pay the donation to the first university with two coins: one of denomination 2 and one of denomination 3 berubleys. The donation to the second university cannot be paid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It's the academic year's end, fateful moment of your school report.
The averages must be calculated. All the students come to you and entreat you to calculate their average for them.
Easy ! You just need to write a script.

Return the average of the given array rounded **down** to its nearest integer.

The array will never be empty.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your program fails again. This time it gets "Wrong answer on test 233".

This is the easier version of the problem. In this version $1 \le n \le 2000$. You can hack this problem only if you solve and lock both problems.

The problem is about a test containing $n$ one-choice-questions. Each of the questions contains $k$ options, and only one of them is correct. The answer to the $i$-th question is $h_{i}$, and if your answer of the question $i$ is $h_{i}$, you earn $1$ point, otherwise, you earn $0$ points for this question. The values $h_1, h_2, \dots, h_n$ are known to you in this problem.

However, you have a mistake in your program. It moves the answer clockwise! Consider all the $n$ answers are written in a circle. Due to the mistake in your program, they are shifted by one cyclically.

Formally, the mistake moves the answer for the question $i$ to the question $i \bmod n + 1$. So it moves the answer for the question $1$ to question $2$, the answer for the question $2$ to the question $3$, ..., the answer for the question $n$ to the question $1$.

We call all the $n$ answers together an answer suit. There are $k^n$ possible answer suits in total.

You're wondering, how many answer suits satisfy the following condition: after moving clockwise by $1$, the total number of points of the new answer suit is strictly larger than the number of points of the old one. You need to find the answer modulo $998\,244\,353$.

For example, if $n = 5$, and your answer suit is $a=[1,2,3,4,5]$, it will submitted as $a'=[5,1,2,3,4]$ because of a mistake. If the correct answer suit is $h=[5,2,2,3,4]$, the answer suit $a$ earns $1$ point and the answer suite $a'$ earns $4$ points. Since $4 > 1$, the answer suit $a=[1,2,3,4,5]$ should be counted.


-----Input-----

The first line contains two integers $n$, $k$ ($1 \le n \le 2000$, $1 \le k \le 10^9$) — the number of questions and the number of possible answers to each question.

The following line contains $n$ integers $h_1, h_2, \dots, h_n$, ($1 \le h_{i} \le k)$ — answers to the questions.


-----Output-----

Output one integer: the number of answers suits satisfying the given condition, modulo $998\,244\,353$.


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

Output
9

Input
5 5
1 1 4 2 2

Output
1000



-----Note-----

For the first example, valid answer suits are $[2,1,1], [2,1,2], [2,1,3], [3,1,1], [3,1,2], [3,1,3], [3,2,1], [3,2,2], [3,2,3]$.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A large banner with word CODEFORCES was ordered for the 1000-th onsite round of Codeforcesω that takes place on the Miami beach. Unfortunately, the company that made the banner mixed up two orders and delivered somebody else's banner that contains someone else's word. The word on the banner consists only of upper-case English letters.

There is very little time to correct the mistake. All that we can manage to do is to cut out some substring from the banner, i.e. several consecutive letters. After that all the resulting parts of the banner will be glued into a single piece (if the beginning or the end of the original banner was cut out, only one part remains); it is not allowed change the relative order of parts of the banner (i.e. after a substring is cut, several first and last letters are left, it is allowed only to glue the last letters to the right of the first letters). Thus, for example, for example, you can cut a substring out from string 'TEMPLATE' and get string 'TEMPLE' (if you cut out string AT), 'PLATE' (if you cut out TEM), 'T' (if you cut out EMPLATE), etc.

Help the organizers of the round determine whether it is possible to cut out of the banner some substring in such a way that the remaining parts formed word CODEFORCES.

Input Specification:
The single line of the input contains the word written on the banner. The word only consists of upper-case English letters. The word is non-empty and its length doesn't exceed 100 characters. It is guaranteed that the word isn't word CODEFORCES.

Output Specification:
Print 'YES', if there exists a way to cut out the substring, and 'NO' otherwise (without the quotes).

Demo Input:
['CODEWAITFORITFORCES\n', 'BOTTOMCODER\n', 'DECODEFORCES\n', 'DOGEFORCES\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
If you have completed the Tribonacci sequence kata, you would know by now that mister Fibonacci has at least a bigger brother. If not, give it a quick look to get how things work.

Well, time to expand the family a little more: think of a Quadribonacci starting with a signature of 4 elements and each following element is the sum of the 4 previous, a Pentabonacci (well *Cinquebonacci* would probably sound a bit more italian, but it would also sound really awful) with a signature of 5 elements and each following element is the sum of the 5 previous, and so on.

Well, guess what? You have to build a Xbonacci function that takes a **signature** of X elements *- and remember each next element is the sum of the last X elements -* and returns the first **n** elements of the so seeded sequence.

```
xbonacci {1,1,1,1} 10 = {1,1,1,1,4,7,13,25,49,94}
xbonacci {0,0,0,0,1} 10 = {0,0,0,0,1,1,2,4,8,16}
xbonacci {1,0,0,0,0,0,1} 10 = {1,0,0,0,0,0,1,2,3,6}
xbonacci {1,1} produces the Fibonacci sequence
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ cities in the Magical Island, numbered from $1$ to $n$. These cities are connected by $m$ bi-directional roads such that there exists a path between every pair of cities. There may be multiple roads between two cities. Each road has a positive length.

Magical crystals are the most important resources transported between the cities in the Magical Island. The cost of sending one magical crystal from city $s$ to city $t$ equals the smallest distance of any path between city $s$ and city $t$. The distance of a path in the Magical Island is a bit special though: It is the bitwise OR value of all the road lengths on this path.

In each of the next $q$ days, exactly one magical crystal will be transported between a pair of cities. Help the Magical Island figure out the transportation cost for each day.

-----Input-----
The first line contains two integers $n, m$ ($2\leq n\leq 10^5,1\leq m\leq n+200$). Each of the next $m$ lines contains three integers $a, b, w$ that describe a road connecting city $a$ and city $b$ with length $w$ ($1\leq a, b\leq n, a \neq b, 1\leq w \leq 10^9$). In the next line, there is a single integer $q$ $(1\leq q\leq 10000)$, the number of days to consider. The next $q$ lines each have two integers $s$ and $t$ ($1\leq s, t\leq n, s \neq t$). The $i$th line indicates that on day $i$ a crystal is sent from city $s$ to city $t$.

-----Output-----
For each of the $q$ days, output the cost of sending the crystal from $s$ to $t$ for that day.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:


Input: [10,2]
Output: "210"

Example 2:


Input: [3,30,34,5,9]
Output: "9534330"


Note: The result may be very large, so you need to return a string instead of an integer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S and two integers L and R. Print the characters in the range L to R of the string.
NOTE: Assume zero based indexing.
Example 1:
Input: 
S = "cdbkdub"
L = 0 , R = 5
Output: "cdbkdu" 
Explanation: Starting from index 0 ('c')
to index 5 ('u').
Example 2:
Input: 
S = "sdiblcsdbud"
L = 3 , R = 7
Output: "blcsd"
Explanation: Starting from index 3 ('b')
to index 7 ('d').
Your Task:  
You dont need to read input or print anything. Complete the function javaSub() which takes S, L, R as input parameter and returns the sting from the range L to R.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)
Constraints:
1<= |S| <=1000
1 <= L <= 800
1 <= R <= 900

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a fishing contest, the participants fish in a lake, represented as a 2D grid of dimension $r \times c$. Each integer point in the grid contains fish. 

At point $(x, y)$, fish first appear at second $t_{x, y}$ and disappear just before time $t_{x, y} + k$ seconds. Outside of this time, no fish can be caught at this position. It takes no time to catch all the fish at a point, and all points contain the same amount of fish. Furthermore, moving to the point immediately north, west, south or east from the point you are currently at takes exactly $1$ second (though you are not required to move).

Assume that you start at some position $(x_0, y_0)$ at second $1$, and can catch fish until (and including) second $l$. From how many points in the lake can you catch fish, if you travel optimally on the lake?

-----Input-----
The input consists of:
 - one line with the integers $r$, $c$, $k$ and $l$ ($1 \le r, c \le 100$, $1 \le k \le 5$, $1 \le l \le 10^5$), the dimensions of the lake, the number of seconds fish stays at a point, and the number of seconds you can catch fish.
 - one line with the integers $x_0$ and $y_0$ ($0 \le x_0 < r$, $0 \le y_0 < c$), your original position.
 - $r$ lines, the $x$’th of which contains $c$ integers $t_{x, 0}, \dots , t_{x, c - 1}$ (each between $1$ and $l$, inclusive), the times at which fish appears on points in the $x$’th row.

-----Output-----
Output the maximum number of points you could catch fish from.

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

Sample Input 2:
2 3 5 6
1 1
1 1 6
1 2 2
Sample Output 2:
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One way to create a task is to learn from life. You can choose some experience in real life, formalize it and then you will get a new task.

Let's think about a scene in real life: there are lots of people waiting in front of the elevator, each person wants to go to a certain floor. We can formalize it in the following way. We have n people standing on the first floor, the i-th person wants to go to the f_{i}-th floor. Unfortunately, there is only one elevator and its capacity equal to k (that is at most k people can use it simultaneously). Initially the elevator is located on the first floor. The elevator needs |a - b| seconds to move from the a-th floor to the b-th floor (we don't count the time the people need to get on and off the elevator).

What is the minimal number of seconds that is needed to transport all the people to the corresponding floors and then return the elevator to the first floor?


-----Input-----

The first line contains two integers n and k (1 ≤ n, k ≤ 2000) — the number of people and the maximal capacity of the elevator.

The next line contains n integers: f_1, f_2, ..., f_{n} (2 ≤ f_{i} ≤ 2000), where f_{i} denotes the target floor of the i-th person.


-----Output-----

Output a single integer — the minimal time needed to achieve the goal.


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

Output
8

Input
4 2
50 100 50 100

Output
296

Input
10 3
2 2 2 2 2 2 2 2 2 2

Output
8



-----Note-----

In first sample, an optimal solution is:   The elevator takes up person #1 and person #2.  It goes to the 2nd floor.  Both people go out of the elevator.  The elevator goes back to the 1st floor.  Then the elevator takes up person #3.  And it goes to the 2nd floor.  It picks up person #2.  Then it goes to the 3rd floor.  Person #2 goes out.  Then it goes to the 4th floor, where person #3 goes out.  The elevator goes back to the 1st floor.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given four integers $a$, $b$, $x$ and $y$. Initially, $a \ge x$ and $b \ge y$. You can do the following operation no more than $n$ times:

  Choose either $a$ or $b$ and decrease it by one. However, as a result of this operation, value of $a$ cannot become less than $x$, and value of $b$ cannot become less than $y$. 

Your task is to find the minimum possible product of $a$ and $b$ ($a \cdot b$) you can achieve by applying the given operation no more than $n$ times.

You have to answer $t$ independent test cases.


-----Input-----

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

The only line of the test case contains five integers $a$, $b$, $x$, $y$ and $n$ ($1 \le a, b, x, y, n \le 10^9$). Additional constraint on the input: $a \ge x$ and $b \ge y$ always holds.


-----Output-----

For each test case, print one integer: the minimum possible product of $a$ and $b$ ($a \cdot b$) you can achieve by applying the given operation no more than $n$ times.


-----Example-----
Input
7
10 10 8 5 3
12 8 8 7 2
12343 43 4543 39 123212
1000000000 1000000000 1 1 1
1000000000 1000000000 1 1 1000000000
10 11 2 1 5
10 11 9 1 10

Output
70
77
177177
999999999000000000
999999999
55
10



-----Note-----

In the first test case of the example, you need to decrease $b$ three times and obtain $10 \cdot 7 = 70$.

In the second test case of the example, you need to decrease $a$ one time, $b$ one time and obtain $11 \cdot 7 = 77$.

In the sixth test case of the example, you need to decrease $a$ five times and obtain $5 \cdot 11 = 55$.

In the seventh test case of the example, you need to decrease $b$ ten times and obtain $10 \cdot 1 = 10$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an undirected graph consisting of n vertices and m edges.

Recall that a cycle is a path that starts and ends in the same vertex. A cycle in a graph is called simple if it contains each vertex (except the starting and ending one) no more than once (the starting and the ending one is contained always twice). Note that loops are considered to be simple cycles.

In one move you can choose any simple cycle in this graph and erase the edges corresponding to this cycle (corresponding vertices remain in the graph). It is allowed to erase the loop or two copies of the same edge (take a look at examples).

Your problem is to apply some sequence of moves to obtain the graph without edges. It is not necessary to minimize the number of cycles. If it is impossible, print "NO".

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 2 ⋅ 10^5) — the number of vertices and the number of edges in the graph.

The next m lines contain edges of the graph. The i-th line contains the i-th edge x_i, y_i (1 ≤ x_i, y_i ≤ n), where x_i and y_i are vertices connected by the i-th edge. The graph can contain loops or multiple edges.

Output

If it is impossible to decompose the given graph into simple cycles, print "NO" in the first line.

Otherwise print "YES" in the first line. In the second line print k — the number of simple cycles in the graph decomposition.

In the next k lines print cycles themselves. The j-th line should contain the j-th cycle. First, print c_j — the number of vertices in the j-th cycle. Then print the cycle as a sequence of vertices. All neighbouring (adjacent) vertices in the printed path should be connected by an edge that isn't contained in other cycles.

Examples

Input


6 9
1 2
2 3
1 3
2 4
2 5
4 5
3 5
3 6
5 6


Output


YES
3
4 2 5 4 2 
4 3 6 5 3 
4 1 3 2 1 


Input


4 7
1 1
1 2
2 3
3 4
4 1
1 3
1 3


Output


YES
3
2 1 1 
5 1 4 3 2 1 
3 1 3 1 


Input


4 8
1 1
1 2
2 3
3 4
4 1
2 4
1 3
1 3


Output


NO

Note

The picture corresponding to the first example: <image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef made two laddus with sweetness X and Y respectively. Cheffina comes and sees the chef created two laddus with different sweetness (might be same). Cheffina has the magical power to make the sweetness of laddus equal. Cheffina requires 1 unit of power to increase the sweetness of laddu by its original value i.e. 1 unit to convert Z to 2Z and 2 unit to convert Z to 3Z and so on… How many units of power does cheffina want to make the sweetness equal?

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, two integers $X, Y$. 

-----Output:-----
For each test case, output in a single line answer as power required.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1 \leq X,Y \leq 10^5$

-----Sample Input:-----
2
2 2
4 6

-----Sample Output:-----
0
3

-----EXPLANATION:-----
For 1) Sweetness are same so no need to use power.
For 2) 
1st laddu
2 Unit power = 4 -> 12
2nd Laddu
1 Unit power = 6 -> 12
After using total 3 unit power sweetness of both laddus are same.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Build a function `sumNestedNumbers`/`sum_nested_numbers` that finds the sum of all numbers in a series of nested arrays raised to the power of their respective nesting levels.  Numbers in the outer most array should be raised to the power of 1.

For example,

should return `1 + 2*2 + 3 + 4*4 + 5*5*5 === 149`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider the array $a$ composed of all the integers in the range $[l, r]$. For example, if $l = 3$ and $r = 7$, then $a = [3, 4, 5, 6, 7]$.

Given $l$, $r$, and $k$, is it possible for $\gcd(a)$ to be greater than $1$ after doing the following operation at most $k$ times?

Choose $2$ numbers from $a$.

Permanently remove one occurrence of each of them from the array.

Insert their product back into $a$.

$\gcd(b)$ denotes the greatest common divisor (GCD) of the integers in $b$.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. The description of test cases follows.

The input for each test case consists of a single line containing $3$ non-negative integers $l$, $r$, and $k$ ($1 \leq l \leq r \leq 10^9, \enspace 0 \leq k \leq r - l$).


-----Output-----

For each test case, print "YES" if it is possible to have the GCD of the corresponding array greater than $1$ by performing at most $k$ operations, and "NO" otherwise (case insensitive).


-----Examples-----

Input
9
1 1 0
3 5 1
13 13 0
4 4 0
3 7 4
4 10 3
2 4 0
1 7 3
1 5 3
Output
NO
NO
YES
YES
YES
YES
NO
NO
YES


-----Note-----

For the first test case, $a = [1]$, so the answer is "NO", since the only element in the array is $1$.

For the second test case the array is $a = [3, 4, 5]$ and we have $1$ operation. After the first operation the array can change to: $[3, 20]$, $[4, 15]$ or $[5, 12]$ all of which having their greatest common divisor equal to $1$ so the answer is "NO".

For the third test case, $a = [13]$, so the answer is "YES", since the only element in the array is $13$.

For the fourth test case, $a = [4]$, so the answer is "YES", since the only element in the array is $4$.

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