vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You have unlimited number of coins with values $1, 2, \ldots, n$. You want to select some set of coins having the total value of $S$. 

It is allowed to have multiple coins with the same value in the set. What is the minimum number of coins required to get sum $S$?


-----Input-----

The only line of the input contains two integers $n$ and $S$ ($1 \le n \le 100\,000$, $1 \le S \le 10^9$)


-----Output-----

Print exactly one integer — the minimum number of coins required to obtain sum $S$.


-----Examples-----
Input
5 11

Output
3
Input
6 16

Output
3


-----Note-----

In the first example, some of the possible ways to get sum $11$ with $3$ coins are: 

  $(3, 4, 4)$

 $(2, 4, 5)$

 $(1, 5, 5)$

 $(3, 3, 5)$ 

It is impossible to get sum $11$ with less than $3$ coins.

In the second example, some of the possible ways to get sum $16$ with $3$ coins are: 

  $(5, 5, 6)$

 $(4, 6, 6)$ 

It is impossible to get sum $16$ with less than $3$ coins.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a binary string A, let f(A) denote its *badness*, defined to be the difference between the number of zeros and number of ones present in it. That is, if the string has c_{0} zeros and c_{1} ones, its badness is |c_{0} - c_{1}|. For example, the badness of "01" is |1 - 1| = 0, the badness of "100" is |2 - 1| = 1, the badness of "1101" is |1 - 3| = 2, and the badness of the empty string is |0 - 0| = 0.

You are given an integer N and a binary string S. 

You would like to partition S into K disjoint [subsequences] (some of which may be empty), such that the maximum badness among all these K subsequences is minimized. Find this value.

Formally,
Let S_{1}, S_{2}, \ldots, S_{K} be a partition of S into disjoint subsequences. Every character of S must appear in one of the S_{i}. Some of the S_{i} may be empty.
Then, find the *minimum* value of \max(f(S_{1}), f(S_{2}), \ldots, f(S_{K})) across all possible choices of S_{1}, S_{2}, \ldots, S_{K} satisfying the first condition.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- The description of each test case is as follows: 
- The first line contains two space-separated integers N and K.
- The second line contains the binary string S of length N.

------ Output Format ------ 

​For each test case, print the minimum possible value of the maximum badness when S is partitioned into K subsequences.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ K ≤ 10^{9}$
$S$ is a binary string, i.e, contains only the characters $0$ and $1$
- The sum of $N$ across all test cases doesn't exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
3
7 5
1010100
4 1
1100
6 2
101111
----- Sample Output 1 ------ 
1
0
2
----- explanation 1 ------ 
Test case $1$: Let's take a couple of examples.
- Suppose the partition is $\{"10", "10", "0", "10", "\ "\}$, obtained as $\textcolor{red}{10}\textcolor{blue}{10}\textcolor{orange}{10}0$ (elements of one color form a subsequence). The respective badness values are $\{0, 0, 1, 0, 0\}$, the maximum of which is $1$.
- Suppose the partition is $\{"101", "00", "\ ", "10", "\ "\}$, obtained as $\textcolor{red}{10}10\textcolor{red}{1}\textcolor{blue}{00}$. The respective badness values are $\{1, 2, 0, 0, 0\}$, the maximum of which is $2$.

The first partition, with a maximum badness of $1$, is one of the optimal partitions.

Test case $2$: The only possible partition is $\{"1100"\}$, which has a badness of $0$.

Test case $3$: The partitions $\{"1011", "11"\}$ and $\{"0111", "11"\}$ both lead to a badness of $\max(2, 0) = 2$, which is the minimum possible.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three integers A, B and C.
Determine whether C is not less than A and not greater than B.

-----Constraints-----
 - -100≤A,B,C≤100 
 - A, B and C are all integers.

-----Input-----
Input is given from Standard Input in the following format:  
A B C

-----Output-----
If the condition is satisfied, print Yes; otherwise, print No.

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

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

C=2 is not less than A=1 and not greater than B=3, and thus the output should be Yes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Monocarp has been collecting rare magazines for quite a while, and now he has decided to sell them. He distributed the magazines between $n$ boxes, arranged in a row. The $i$-th box contains $a_i$ magazines. Some of the boxes are covered with lids, others are not.

Suddenly it started to rain, and now Monocarp has to save as many magazines from the rain as possible. To do this, he can move the lids between boxes as follows: if the $i$-th box was covered with a lid initially, he can either move the lid from the $i$-th box to the box $(i-1)$ (if it exists), or keep the lid on the $i$-th box. You may assume that Monocarp can move the lids instantly at the same moment, and no lid can be moved more than once. If a box will be covered with a lid after Monocarp moves the lids, the magazines in it will be safe from the rain; otherwise they will soak.

You have to calculate the maximum number of magazines Monocarp can save from the rain.


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of the testcases.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of boxes.

The second line contains a string of $n$ characters 0 and/or 1. If the $i$-th character is 1, the $i$-th box is initially covered with a lid. If the $i$-th character is 0, the $i$-th box is initially not covered.

The third line contains a sequence of integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$), where $a_i$ is the number of magazines in the $i$-th box.

The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each testcase, print one integer — the maximum number of magazines Monocarp can save from the rain.


-----Examples-----

Input
4
5
01110
10 5 8 9 6
6
011011
20 10 9 30 20 19
4
0000
100 100 100 100
4
0111
5 4 5 1
Output
27
80
0
14


-----Note-----

In the first testcase of the example, Monocarp can move the lid from the second box to the first box, so the boxes $1$, $3$ and $4$ are covered, and $10 + 8 + 9 = 27$ magazines are saved.

In the second testcase, Monocarp can move the lid from the second box to the first box, then from the third box to the second box, then from the fifth box to the fourth box, and then from the sixth box to the fifth box. The boxes $1$, $2$, $4$ and $5$ will be covered, so $20 + 10 + 30 + 20 = 80$ magazines can be saved.

There are no lids in the third testcase, so it's impossible to save even a single magazine.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Let's Watch Football

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Valeric and Valerko missed the last Euro football game, so they decided to watch the game's key moments on the Net. They want to start watching as soon as possible but the connection speed is too low. If they turn on the video right now, it will "hang up" as the size of data to watch per second will be more than the size of downloaded data per second.

The guys want to watch the whole video without any pauses, so they have to wait some integer number of seconds for a part of the video to download. After this number of seconds passes, they can start watching. Waiting for the whole video to download isn't necessary as the video can download after the guys started to watch.

Let's suppose that video's length is *c* seconds and Valeric and Valerko wait *t* seconds before the watching. Then for any moment of time *t*0, *t*<=≤<=*t*0<=≤<=*c*<=+<=*t*, the following condition must fulfill: the size of data received in *t*0 seconds is not less than the size of data needed to watch *t*0<=-<=*t* seconds of the video.

Of course, the guys want to wait as little as possible, so your task is to find the minimum integer number of seconds to wait before turning the video on. The guys must watch the video without pauses.

Input Specification:
The first line contains three space-separated integers *a*, *b* and *c* (1<=≤<=*a*,<=*b*,<=*c*<=≤<=1000,<=*a*<=&gt;<=*b*). The first number (*a*) denotes the size of data needed to watch one second of the video. The second number (*b*) denotes the size of data Valeric and Valerko can download from the Net per second. The third number (*c*) denotes the video's length in seconds.

Output Specification:
Print a single number — the minimum integer number of seconds that Valeric and Valerko must wait to watch football without pauses.

Demo Input:
['4 1 1\n', '10 3 2\n', '13 12 1\n']

Demo Output:
['3\n', '5\n', '1\n']

Note:
In the first sample video's length is 1 second and it is necessary 4 units of data for watching 1 second of video, so guys should download 4 · 1 = 4 units of data to watch the whole video. The most optimal way is to wait 3 seconds till 3 units of data will be downloaded and then start watching. While guys will be watching video 1 second, one unit of data will be downloaded and Valerik and Valerko will have 4 units of data by the end of watching. Also every moment till the end of video guys will have more data then necessary for watching.

In the second sample guys need 2 · 10 = 20 units of data, so they have to wait 5 seconds and after that they will have 20 units before the second second ends. However, if guys wait 4 seconds, they will be able to watch first second of video without pauses, but they will download 18 units of data by the end of second second and it is less then necessary.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your parents decided that it would be “fun” to spend the entire Sunday walking near the Mookerheide close to Nijmegen.

Although you can pass the time by solving programming problems in your head, your siblings do not have the same luxury. After a short while, your younger sister Alice and your big brother Bob find themselves hopelessly bored. Together, they try to figure out if they can pass the time with a game (a problem that would later be referred to as the Bob and Alice Pastime Conundrum). Finally, they come up with the following simple game.

They find a single branch of length $n$ that will be the main object of the game. Alternatingly, Alice and Bob choose a piece of branch and break it into two parts, in such a way that both parts have integer lengths. The last player who is able to break one of the pieces wins. Alice gets to start, as she is the younger of the two.

Of course, you already have the game figured out in your head. Assuming Bob plays optimally, can Alice win the game? And if so, what move should she make first?

-----Input-----
 - A line containing a single integer $2\leq n\leq 10^9$, the length of the branch.

-----Output-----
 - On the first line print the name of the person who wins, Alice or Bob.
 - If Alice can win, print the length of a piece of branch Alice can break off as a winning move. This should be an integer between $1$ and $n-1$, inclusive.

If there are multiple valid solutions, you may output any one of them.

-----Examples-----
Sample Input:
2
Sample Output:
Alice
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider a sequence, $c_0,c_1,\ldots c_{n-1}$, and a polynomial of degree $1$ defined as $Q(x)=a\cdot x+b$. You must perform $\textit{q}$ queries on the sequence, where each query is one of the following two types:

1 i x: Replace $c_i$ with $\boldsymbol{x}$.
2 l r: Consider the polynomial $P(x)=c_l\cdot x^0+c_{l+1}\cdot x^1+\cdots+c_r\cdot x^{r-l}$ and determine whether $P(x)$ is divisible by $Q(x)=a\cdot x+b$ over the field $Z_p$, where $p=10^9+7$. In other words, check if there exists a polynomial $R(x)$ with integer coefficients such that each coefficient of $P(x)-R(x)\cdot Q(x)$ is divisible by $\boldsymbol{p}$. If a valid $R(x)$ exists, print Yes on a new line; otherwise, print No.

Given the values of $n$, $\class{ML__boldsymbol}{\boldsymbol{a}}$, $\boldsymbol{b}$, and $\textit{q}$ queries, perform each query in order.

Input Format

The first line contains four space-separated integers describing the respective values of $n$ (the length of the sequence), $\class{ML__boldsymbol}{\boldsymbol{a}}$ (a coefficient in $Q(x)$), $\boldsymbol{b}$ (a coefficient in $Q(x)$), and $\textit{q}$ (the number of queries). 

The second line contains $n$ space-separated integers describing $c_0,c_1,\ldots c_{n-1}$. 

Each of the $\textit{q}$ subsequent lines contains three space-separated integers describing a query of either type 1 or type 2.

Constraints

$1\leq n,q\leq10^5$
For query type 1: $0\leq i\leq n-1$ and $0\leq x<10^9+7$.
For query type 2: $0\leq l\leq r\leq n-1$.
$0\leq a,b,c_i<10^9+7$
$a\neq0$

Output Format

For each query of type 2, print Yes on a new line if $Q(x)$ is a divisor of $P(x)$; otherwise, print No instead.

Sample Input 0
3 2 2 3
1 2 3
2 0 2
1 2 1
2 0 2

Sample Output 0
No
Yes

Explanation 0

Given $Q(x)=2\cdot x+2$ and the initial sequence $c=\{1,2,3\}$, we perform the following $q=3$ queries:

$Q(x)=2\cdot x+2$ is not a divisor of $P(x)=1+2\cdot x+3\cdot x^2$, so we print No on a new line.
Set $c_2$ to $1$, so $c=\{1,2,1\}$.
After the second query, $P(x)=1+2\cdot x+1\cdot x^2$. Because $(2\cdot x+2)\cdot(500000004\cdot x+500000004)\text{mod}(10^9+7)=1+2\cdot x+1\cdot x^2=P(x)$, we print Yes on a new line.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Based on [this kata, Connect Four.](https://www.codewars.com/kata/connect-four-1)

In this kata we play a modified game of connect four. It's connect X, and there can be multiple players.

Write the function ```whoIsWinner(moves,connect,size)```.

```2 <= connect <= 10```

```2 <= size <= 52```

Each column is identified by a character, A-Z a-z:  
``` ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz ```


Moves come in the form:

```
['C_R','p_Y','s_S','I_R','Z_Y','d_S']
```
* Player R puts on C
* Player Y puts on p
* Player S puts on s
* Player R puts on I
* ...

The moves are in the order that they are played. 

The first player who connect ``` connect ``` items in same color is the winner. 

Note that a player can win before all moves are done. You should return the first winner.

If no winner is found, return "Draw".

A board with size 7, where yellow has connected 4:

All inputs are valid, no illegal moves are made.

![alt text](https://i.imgur.com/xnJEsIx.png)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a directed graph G which can contain loops (edges from a vertex to itself). Multi-edges are absent in G which means that for all ordered pairs (u, v) exists at most one edge from u to v. Vertices are numbered from 1 to n.

A path from u to v is a sequence of edges such that:

  * vertex u is the start of the first edge in the path; 
  * vertex v is the end of the last edge in the path; 
  * for all pairs of adjacent edges next edge starts at the vertex that the previous edge ends on. 



We will assume that the empty sequence of edges is a path from u to u.

For each vertex v output one of four values:

  * 0, if there are no paths from 1 to v; 
  * 1, if there is only one path from 1 to v; 
  * 2, if there is more than one path from 1 to v and the number of paths is finite; 
  * -1, if the number of paths from 1 to v is infinite. 



Let's look at the example shown in the figure.

<image>

Then:

  * the answer for vertex 1 is 1: there is only one path from 1 to 1 (path with length 0); 
  * the answer for vertex 2 is 0: there are no paths from 1 to 2; 
  * the answer for vertex 3 is 1: there is only one path from 1 to 3 (it is the edge (1, 3)); 
  * the answer for vertex 4 is 2: there are more than one paths from 1 to 4 and the number of paths are finite (two paths: [(1, 3), (3, 4)] and [(1, 4)]); 
  * the answer for vertex 5 is -1: the number of paths from 1 to 5 is infinite (the loop can be used in a path many times); 
  * the answer for vertex 6 is -1: the number of paths from 1 to 6 is infinite (the loop can be used in a path many times). 

Input

The first contains an integer t (1 ≤ t ≤ 10^4) — the number of test cases in the input. Then t test cases follow. Before each test case, there is an empty line.

The first line of the test case contains two integers n and m (1 ≤ n ≤ 4 ⋅ 10^5, 0 ≤ m ≤ 4 ⋅ 10^5) — numbers of vertices and edges in graph respectively. The next m lines contain edges descriptions. Each line contains two integers a_i, b_i (1 ≤ a_i, b_i ≤ n) — the start and the end of the i-th edge. The vertices of the graph are numbered from 1 to n. The given graph can contain loops (it is possible that a_i = b_i), but cannot contain multi-edges (it is not possible that a_i = a_j and b_i = b_j for i ≠ j).

The sum of n over all test cases does not exceed 4 ⋅ 10^5. Similarly, the sum of m over all test cases does not exceed 4 ⋅ 10^5.

Output

Output t lines. The i-th line should contain an answer for the i-th test case: a sequence of n integers from -1 to 2.

Example

Input


5

6 7
1 4
1 3
3 4
4 5
2 1
5 5
5 6

1 0

3 3
1 2
2 3
3 1

5 0

4 4
1 2
2 3
1 4
4 3


Output


1 0 1 2 -1 -1 
1 
-1 -1 -1 
1 0 0 0 0 
1 1 2 1 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Amugae has a sentence consisting of $n$ words. He want to compress this sentence into one word. Amugae doesn't like repetitions, so when he merges two words into one word, he removes the longest prefix of the second word that coincides with a suffix of the first word. For example, he merges "sample" and "please" into "samplease".

Amugae will merge his sentence left to right (i.e. first merge the first two words, then merge the result with the third word and so on). Write a program that prints the compressed word after the merging process ends.


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 10^5$), the number of the words in Amugae's sentence.

The second line contains $n$ words separated by single space. Each words is non-empty and consists of uppercase and lowercase English letters and digits ('A', 'B', ..., 'Z', 'a', 'b', ..., 'z', '0', '1', ..., '9'). The total length of the words does not exceed $10^6$.


-----Output-----

In the only line output the compressed word after the merging process ends as described in the problem.


-----Examples-----
Input
5
I want to order pizza

Output
Iwantorderpizza
Input
5
sample please ease in out

Output
sampleaseinout

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Gru wants to distribute $N$ bananas to $K$ minions on his birthday.
Gru does not like to just give everyone the same number of bananas, so instead, he wants to distribute bananas in such a way that each minion gets a $distinct$ amount of bananas. That is, no two minions should get the same number of bananas.
Gru also loves $gcd$. The higher the $gcd$, the happier Gru and the minions get. So help Gru in distributing the bananas in such a way that each Minion gets a distinct amount of bananas and gcd of this distribution is highest possible. Output this maximum gcd. If such a distribution is not possible output $-1$.
Note: You have to distribute $all$ $N$ bananas. 

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase consists of a single line of input, which has two integers: $N, K$. 

-----Output:-----
For each testcase, output in a single line the maximum gcd or -1.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq N, K \leq 10^9$

-----Sample Input:-----
1
6 3

-----Sample Output:-----
1

-----EXPLANATION:-----
The only possible distribution is $[1, 2, 3]$. So the answer is 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are S sheep and W wolves.
If the number of wolves is greater than or equal to that of sheep, the wolves will attack the sheep.
If the wolves will attack the sheep, print unsafe; otherwise, print safe.

-----Constraints-----
 - 1 \leq S \leq 100
 - 1 \leq W \leq 100

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

-----Output-----
If the wolves will attack the sheep, print unsafe; otherwise, print safe.

-----Sample Input-----
4 5

-----Sample Output-----
unsafe

There are four sheep and five wolves. The number of wolves is not less than that of sheep, so they will attack them.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today, puppy Tuzik is going to a new dog cinema. He has already left his home and just realised that he forgot his dog-collar! This is a real problem because the city is filled with catchers looking for stray dogs.
A city where Tuzik lives in can be considered as an infinite grid, where each cell has exactly four neighbouring cells: those sharing a common side with the cell. Such a property of the city leads to the fact, that the distance between cells (xA, yA) and (xB, yB) equals |xA - xB| + |yA - yB|.
Initially, the puppy started at the cell with coordinates (0, 0). There are N dog-catchers located at the cells with the coordinates (xi, yi), where 1 ≤ i ≤ N. Tuzik's path can be described as a string S of M characters, each of which belongs to the set {'D', 'U', 'L', 'R'} (corresponding to it moving down, up, left, and right, respectively). To estimate his level of safety, Tuzik wants to know the sum of the distances from each cell on his path to all the dog-catchers. You don't need to output this sum for the staring cell of the path (i.e. the cell with the coordinates (0, 0)).

-----Input-----
The first line of the input contains two integers N and M.
The following N lines contain two integers xi and yi each, describing coordinates of the dog-catchers.
The last line of the input contains string S of M characters on the set {'D', 'U', 'L', 'R'}.
- 'D' - decrease y by 1
- 'U' - increase y by 1
- 'L' - decrease x by 1
- 'R' - increase x by 1

-----Output-----
Output M lines: for each cell of the path (except the starting cell), output the required sum of the distances.

-----Constraints-----
- 1 ≤ N ≤ 3 ✕ 105
- 1 ≤ M ≤ 3 ✕ 105
- -106 ≤ xi, yi ≤ 106

-----Example-----
Input:
2 3
1 2
0 1
RDL

Output:
4
6
6

-----Explanation-----

Initially Tuzik stays at cell (0, 0). Let's consider his path:

- Move 'R' to the cell (1, 0). Distance to the catcher (1, 2) equals 2, distance to the catcher (0, 1) equals 2, so the total distance equals 4
- Move 'D' to the cell (1, -1). Distance to the catcher (1, 2) equals 3, distance to the catcher (0, 1) equals 3, so the total distance equals 6
- Move 'L' to the cell (0, -1). Distance to the catcher (1, 2) equals 4, distance to the catcher (0, 1) equals 2, so the total distance equals 6

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