vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
In the ancient nation of Iwashiro, priests pray to calm disasters in the event of a disaster.

The priest selects the character string S from the ancient documents and proceeds with the ritual by repeating the following.

* Select one place in the string $ S $, replace the character written there with another character, and update $ S $.
* Find out what kind of string repetitions $ S $ can represent, and recite the found string. However, if $ S $ cannot be represented by repeating a character string, $ S $ is chanted.



Prayer is most effective when you recite the shortest string that represents the original string. For example, for the string abababab, prayer is most effective when you say ab instead of the string itself or abab.

As a novice priest, you must learn how to quickly find the string that maximizes the effectiveness of your prayers from the given string $ S $.

Given some information about the string $ S $ and the replacement of characters. Create a program that finds the length of the string that maximizes the effectiveness of prayer for the resulting string each time you swap characters.



input

The input is given in the following format.


$ N $ $ Q $
$ S $
$ p_1 $ $ c_1 $
$ p_2 $ $ c_2 $
::
$ p_Q $ $ c_Q $


The length of the string $ N $ ($ 2 \ leq N \ leq 10 ^ 5 $) and the number of character swaps $ Q $ ($ 1 \ leq Q \ leq 10 ^ 5 $) are given on the first line. The second line is given a string $ S $ of length $ N $ consisting of lowercase letters. The following $ Q $ line is given the position of the character to be replaced at the $ i $ th position $ p_i $ ($ 1 \ leq p_i \ leq N $) and the character $ c_i $ after the replacement. However, $ p_i $ is represented by the number from the left end of the character string. Also, $ c_i $ is lowercase.

output

Each time the characters are replaced, the length of the character string that maximizes the effect of prayer for the obtained character string is output on one line.

Examples

Input

6 5
ababac
6 b
3 c
4 a
5 b
6 c


Output

2
6
6
6
3


Input

None


Output

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Welcome to the Codewars Bar!

Codewars Bar recommends you drink 1 glass of water per standard drink so you're not hungover tomorrow morning.

Your fellow coders have bought you several drinks tonight in the form of a string. Return a string suggesting how many glasses of water you should drink to not be hungover.

## Examples

```
"1 beer"  =>  "1 glass of water"
"1 shot, 5 beers and 1 glass of wine"  =>  "7 glasses of water"
```

## Notes

* To keep the things simple, we'll consider that anything with a number in front of it is a drink: `"1 bear" => "1 glass of water"` or `"1 chainsaw and 2 pools" => "3 glasses of water"`
* The number in front of each drink lies in range `[1; 9]`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Non-square Equation

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Let's consider equation:

where *x*,<=*n* are positive integers, *s*(*x*) is the function, equal to the sum of digits of number *x* in the decimal number system.

You are given an integer *n*, find the smallest positive integer root of equation *x*, or else determine that there are no such roots.

Input Specification:
A single line contains integer *n* (1<=≤<=*n*<=≤<=1018) — the equation parameter.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Output Specification:
Print -1, if the equation doesn't have integer positive roots. Otherwise print such smallest integer *x* (*x*<=&gt;<=0), that the equation given in the statement holds.

Demo Input:
['2\n', '110\n', '4\n']

Demo Output:
['1\n', '10\n', '-1\n']

Note:
In the first test case *x* = 1 is the minimum root. As *s*(1) = 1 and 1<sup class="upper-index">2</sup> + 1·1 - 2 = 0.

In the second test case *x* = 10 is the minimum root. As *s*(10) = 1 + 0 = 1 and 10<sup class="upper-index">2</sup> + 1·10 - 110 = 0.

In the third test case the equation has no roots.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a set of points on a plane with positive integer coordinates. Find a triangle of minimum area with vertices in points (0, 0), (A, 0) and (0, B) (A and B are unknown positive integers) that contains all the given points inside it (points on the edges count towards being inside).

Input

The first line of the input contains an integer N (1 ≤ N ≤ 100) — the number of points. The following N lines contain pairs of numbers X and Y (1 ≤ X, Y ≤ 100) - the coordinates of the points. All points are distinct.

Output

Output one floating-point number — the minimal area of the triangle. The answer is considered to be correct if its absolute or relative error does not exceed 10 - 4.

Examples

Input

2
1 1
1 3


Output

6.0


Input

2
2 1
1 2


Output

4.5

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarp has created his own training plan to prepare for the programming contests. He will train for $n$ days, all days are numbered from $1$ to $n$, beginning from the first.

On the $i$-th day Polycarp will necessarily solve $a_i$ problems. One evening Polycarp plans to celebrate the equator. He will celebrate it on the first evening of such a day that from the beginning of the training and to this day inclusive he will solve half or more of all the problems.

Determine the index of day when Polycarp will celebrate the equator.

Input Specification:
The first line contains a single integer $n$ ($1 \le n \le 200\,000$) — the number of days to prepare for the programming contests.

The second line contains a sequence $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10\,000$), where $a_i$ equals to the number of problems, which Polycarp will solve on the $i$-th day.

Output Specification:
Print the index of the day when Polycarp will celebrate the equator.

Demo Input:
['4\n1 3 2 1\n', '6\n2 2 2 2 2 2\n']

Demo Output:
['2\n', '3\n']

Note:
In the first example Polycarp will celebrate the equator on the evening of the second day, because up to this day (inclusive) he will solve $4$ out of $7$ scheduled problems on four days of the training.

In the second example Polycarp will celebrate the equator on the evening of the third day, because up to this day (inclusive) he will solve $6$ out of $12$ scheduled problems on six days of the training.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This kata is based on a [variation](https://www.codewars.com/kata/happy-numbers-5) of *Happy Numbers* by TySlothrop. It is advisable to complete it first to grasp the idea and then move on to this one.

___

Hello, my dear friend, and welcome to another *Happy Numbers* kata! What? You're not interested in them anymore? They are all the same? But what if I say that this one is a *performance version*...  

___

# Your task:

Write a function `performant_numbers` which takes a number `n` as an argument and returns a list of all *happy numbers* from `1` to `n` inclusive. For example:

```
performant_numbers(10)   =>  [1, 7, 10]
performant_numbers(50)   =>  [1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49]
performant_numbers(100)  =>  [1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100]
```

# Test suite:

* `5000` tests with number `n` being up to `300000`
* The reference solution takes around `4.9` seconds to calculate the result
* you are not allowed to hardcode the sequence: you'll have to compute it (max length of the code: 1700 characters)

___

Will you take up the challenge?

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rhymes are complicated. The extent to which one word rhymes with another depends on how similar they sound; but if they are too similar then they aren’t considered a rhyme at all. Karim has a huge list of $N$ words and wants to determine the maximally rhyming pair of words. To that end he has introduced the concept of rhyme power:

Given two words $S$ and $T$, their rhyme power $r(S,T)$ is defined as
 - $0$, if one word is a suffix of the other,
 - the length of their longest common suffix, otherwise.

For instance, the rhyme power of “fire” and “desire” is $3$, because their longest common suffix “ire” has length $3$. In contrast, the rhyme power of “impossible” and “possible” is $0$, because “possible” is a suffix of “impossible”.

Given Karim’s list of $N$ words, your task is to find the maximum value of $r(S, T)$ over all pairs of words.

-----Input-----
The first line contains an integer $N$ with $2 \leq N \leq 10^5$, the number of words.

The following $N$ lines each contain a string $S_ i$, where $1 \leq |S_ i| \leq 10^6$. The sum of all string lengths $|S_ i|$ is at most $10^6$.

-----Output-----
An integer, the maximal rhyme power.

-----Examples-----
Sample Input:
4
spaghetti
already
confetti
serengeti
Sample Output:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef published a blog post, and is now receiving many queries about it. On day $i$, he receives $Q_i$ queries. But Chef can answer at most $k$ queries in a single day. 
Chef always answers the maximum number of questions that he can on any given day (note however that this cannot be more than $k$). The remaining questions (if any) will be carried over to the next day.
Fortunately, after $n$ days, the queries have stopped. Chef would like to know the first day during which he has some free time, i.e. the first day when he answered less than $k$ questions. 

-----Input:-----
- First line will contain $T$, the number of testcases. Then the testcases follow.
- The first line of each testcase contains two space separated integers $n$ and $k$.
- The second line of each testcase contains $n$ space separated integers, namely $Q_1, Q_2, ... Q_n$.

-----Output:-----
For each testcase, output in a single line the first day during which chef answers less than $k$ questions. 

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1 \leq $ sum of $n$ over all testcases $ \leq 10^5$
- $1 \leq k \leq 10^8$
- $0 \leq Q_i \leq 10^8$

-----Subtasks-----
- Subtask 1 - 20% points - Sum of $Q_i$ over all testcases and days $\leq 3 . 10^6$
- Subtask 2 - 80% points - Original constraints

-----Sample Input:-----
2 
6 5 
10 5 5 3 2 1 
1 1
100

-----Sample Output:-----
6
101

-----Explanation:-----
Test Case 1
On the first day, chef answers 5 questions and leaves the remaining 5 (out of the 10) for the future days.
On the second day, chef has 10 questions waiting to be answered (5 received on the second day and 5 unanswered questions from day 1). Chef answers 5 of these questions and leaves the remaining 5 for the future.
On the third day, chef has 10 questions waiting to be answered (5 received on the third day and 5 unanswered questions from earlier). Chef answers 5 of these questions and leaves the remaining 5 for later.
On the fourth day, chef has 8 questions waiting to be answered (3 received on the fourth day and 5 unanswered questions from earlier). Chef answers 5 of these questions and leaves the remaining 3 for later.
On the fifth day, chef has 5 questions waiting to be answered (2 received on the fifth day and 3 unanswered questions from earlier). Chef answers all 5 of these questions.
On the sixth day, chef has 1 question, which he answers. This is the first day he answers less than 5 questions, and so the answer is 6.
Test Case 2
Chef answers 1 question a day for the first 100 days. On day 101, he is free.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Eugeny has n cards, each of them has exactly one integer written on it. Eugeny wants to exchange some cards with Nikolay so that the number of even integers on his cards would equal the number of odd integers, and that all these numbers would be distinct. 

Nikolay has m cards, distinct numbers from 1 to m are written on them, one per card. It means that Nikolay has exactly one card with number 1, exactly one card with number 2 and so on. 

A single exchange is a process in which Eugeny gives one card to Nikolay and takes another one from those Nikolay has. Your task is to find the minimum number of card exchanges and determine which cards Eugeny should exchange.


-----Input-----

The first line contains two integers n and m (2 ≤ n ≤ 2·10^5, 1 ≤ m ≤ 10^9) — the number of cards Eugeny has and the number of cards Nikolay has. It is guaranteed that n is even.

The second line contains a sequence of n positive integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — the numbers on Eugeny's cards.


-----Output-----

If there is no answer, print -1.

Otherwise, in the first line print the minimum number of exchanges. In the second line print n integers — Eugeny's cards after all the exchanges with Nikolay. The order of cards should coincide with the card's order in the input data. If the i-th card wasn't exchanged then the i-th number should coincide with the number from the input data. Otherwise, it is considered that this card was exchanged, and the i-th number should be equal to the number on the card it was exchanged to.

If there are multiple answers, it is allowed to print any of them.


-----Examples-----
Input
6 2
5 6 7 9 4 5

Output
1
5 6 7 9 4 2 

Input
8 6
7 7 7 7 8 8 8 8

Output
6
7 2 4 6 8 1 3 5 

Input
4 1
4 2 1 10

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tejas has invited the Clash Team for a Dinner Party. He places V empty plates (numbered from 1 to V inclusive) in a straight line on a table. He has prepared 2 kinds of Delicious Dishes named dish A and dish B.

He has exactly V servings of Dish A and W servings of dish B. 

Now he wants to serve the dishes in such a way that if theith plate has serving of Dish A then (i-1)th plate should not have serving of Dish B. Assuming all the Dishes are identical find number of ways Tejas can serve the Clash Team.

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases . The description of T testcases follow.

- The first line of each test case contains two space seperated integers V W .

-----Output-----
For each test case, output the number of ways Tejas can serve the Clash Team.


-----Constraints-----

- 1 ≤ T ≤ 100
- 1 ≤ V ≤ 1000
- 1 ≤ W ≤ 1000

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

1

3 3 

Output:
4



-----Explanation-----

In the above example the 4 ways are:

AAA

AAB

ABB

BBB

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a tree. We will consider simple paths on it. Let's denote path between vertices a and b as (a, b). Let d-neighborhood of a path be a set of vertices of the tree located at a distance ≤ d from at least one vertex of the path (for example, 0-neighborhood of a path is a path itself). Let P be a multiset of the tree paths. Initially, it is empty. You are asked to maintain the following queries:

  * 1 u v — add path (u, v) into P (1 ≤ u, v ≤ n). 
  * 2 u v — delete path (u, v) from P (1 ≤ u, v ≤ n). Notice that (u, v) equals to (v, u). For example, if P = \{(1, 2), (1, 2)\}, than after query 2 2 1, P = \{(1, 2)\}. 
  * 3 d — if intersection of all d-neighborhoods of paths from P is not empty output "Yes", otherwise output "No" (0 ≤ d ≤ n - 1). 

Input

The first line contains two integers n and q — the number of vertices in the tree and the number of queries, accordingly (1 ≤ n ≤ 2 ⋅ 10^5, 2 ≤ q ≤ 2 ⋅ 10^5).

Each of the following n - 1 lines contains two integers x_i and y_i — indices of vertices connected by i-th edge (1 ≤ x_i, y_i ≤ n).

The following q lines contain queries in the format described in the statement.

It's guaranteed that: 

  * for a query 2 u v, path (u, v) (or (v, u)) is present in P, 
  * for a query 3 d, P ≠ ∅, 
  * there is at least one query of the third type. 

Output

For each query of the third type output answer on a new line.

Examples

Input


1 4
1 1 1
1 1 1
2 1 1
3 0


Output


Yes


Input


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


Output


No


Input


10 6
1 2
2 3
3 4
4 7
7 10
2 5
5 6
6 8
8 9
1 9 9
1 9 8
1 8 5
3 0
3 1
3 2


Output


No
Yes
Yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Suppose that P1 is an infinite-height prism whose axis is parallel to the z-axis, and P2 is also an infinite-height prism whose axis is parallel to the y-axis. P1 is defined by the polygon C1 which is the cross section of P1 and the xy-plane, and P2 is also defined by the polygon C2 which is the cross section of P2 and the xz-plane.

Figure I.1 shows two cross sections which appear as the first dataset in the sample input, and Figure I.2 shows the relationship between the prisms and their cross sections.

<image>


Figure I.1: Cross sections of Prisms

<image>


Figure I.2: Prisms and their cross sections

<image>


Figure I.3: Intersection of two prisms

Figure I.3 shows the intersection of two prisms in Figure I.2, namely, P1 and P2.

Write a program which calculates the volume of the intersection of two prisms.



Input

The input is a sequence of datasets. The number of datasets is less than 200.

Each dataset is formatted as follows.

m n
x11 y11
x12 y12
.
.
.
x1m y1m
x21 z21
x22 z22
.
.
.
x2n z2n


m and n are integers (3 ≤ m ≤ 100, 3 ≤ n ≤ 100) which represent the numbers of the vertices of the polygons, C1 and C2, respectively.

x1i, y1i, x2j and z2j are integers between -100 and 100, inclusive. (x1i, y1i) and (x2j , z2j) mean the i-th and j-th vertices' positions of C1 and C2 respectively.

The sequences of these vertex positions are given in the counterclockwise order either on the xy-plane or the xz-plane as in Figure I.1.

You may assume that all the polygons are convex, that is, all the interior angles of the polygons are less than 180 degrees. You may also assume that all the polygons are simple, that is, each polygon's boundary does not cross nor touch itself.

The end of the input is indicated by a line containing two zeros.

Output

For each dataset, output the volume of the intersection of the two prisms, P1 and P2, with a decimal representation in a line.

None of the output values may have an error greater than 0.001. The output should not contain any other extra characters.

Example

Input

4 3
7 2
3 3
0 2
3 1
4 2
0 1
8 1
4 4
30 2
30 12
2 12
2 2
15 2
30 8
13 14
2 8
8 5
13 5
21 7
21 9
18 15
11 15
6 10
6 8
8 5
10 12
5 9
15 6
20 10
18 12
3 3
5 5
10 3
10 10
20 8
10 15
10 8
4 4
-98 99
-99 -99
99 -98
99 97
-99 99
-98 -98
99 -99
96 99
0 0


Output

4.708333333333333
1680.0000000000005
491.1500000000007
0.0
7600258.4847715655

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are a seasoned Fight Club member who recently stumbled upon the classified plans of Project Mayhem, a secret organization that the other members have created to bring down consumerism and corporate America. To completely destabilize modern civilization, Tyler Durden and his Project Mayhem trainees are making plans to take down the buildings of major banks that hold everybody’s credit information. If they succeed, then everybody is supposed to restart life with a blank slate, free of all debts ranging from mortgages to student loans.


Tyler plans to do so by setting off pipe bombs under major financial buildings. His crew has mapped out the city’s financial district on a rectangular grid with $R$ rows and $C$ columns. Each grid cell either has a building armed with bombs to detonate (denoted by “x") or does not (denoted by “."). As a friend of Tyler’s, you know all too well that his plan is off the chains. Violence is never the solution. You want to do your best to thwart the plan by visiting the buildings one by one and disarming as many bombs as possible.


You can disarm the buildings in any order, with only one catch. After you disarm a building, Tyler’s crew will find out, chase after you, and occupy that building indefinitely. To avoid getting caught, you must immediately find another (armed) building in the same street or avenue to take cover before disarming other buildings. After that however, you can go to any other armed building on the map to disarm it (provided the same condition is met). In other words, at any time you disarm a building, there must be at least one other armed building in either the same row or the same column.


Take the following $3$ by $3$ map for example:

     x.. .x. x.x

You have a few ways to disarm up to $2$ buildings:
 - You can first disarm the top-left one, followed by either of the bottom two buildings, for a total of $2$ buildings.
 - You can first disarm the bottom-right one, followed by either of the remaining two leftmost buildings, for a total of $2$ buildings.
 - However, note that if you choose to first disarm the bottom-left building, then none of the remaining buildings can be disarmed (since you won’t be able to take cover afterwards). So in this case, you would only be able to disarm a single building.

In any of these cases, the center building can never be disarmed since there is no immediate neighboring building in its row or column to use for cover from Tyler’s henchmen.


Given a map of the city, you would like to know the maximum number of buildings that can be disarmed.

-----Input-----
The first line of input consists of two space-separated integers $R$ and $C$ ($1 \le R, C \le 2000$).

$R$ lines follow, each of which consists of $C$ characters (either “x" or “."), specifying the grid of the financial district.

-----Output-----
Print, on a single line, the maximum number of buildings that can be disarmed.


-----Examples-----
Sample Input:
3 3
x..
.x.
x.x
Sample Output:
2

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Daniel is organizing a football tournament. He has come up with the following tournament format: 
 1.  In the first several (possibly zero) stages, while the number of teams is even, they split in pairs and play one game for each pair. At each stage the loser of each pair is eliminated (there are no draws). Such stages are held while the number of teams is even. 1.  Eventually there will be an odd number of teams remaining. If there is one team remaining, it will be declared the winner, and the tournament ends. Otherwise each of the remaining teams will play with each other remaining team once in round robin tournament (if there are *x* teams, there will be  games), and the tournament ends. 
For example, if there were 20 teams initially, they would begin by playing 10 games. So, 10 teams would be eliminated, and the remaining 10 would play 5 games. Then the remaining 5 teams would play 10 games in a round robin tournament. In total there would be 10+5+10=25 games.

Daniel has already booked the stadium for *n* games. Help him to determine how many teams he should invite so that the tournament needs exactly *n* games. You should print all possible numbers of teams that will yield exactly *n* games in ascending order, or -1 if there are no such numbers.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=1018), the number of games that should be played.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output Specification:
Print all possible numbers of invited teams in ascending order, one per line. If exactly *n* games cannot be played, output one number: -1.

Demo Input:
['3\n', '25\n', '2\n']

Demo Output:
['3\n4\n', '20\n', '-1\n']

Note:
none

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