vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Chef Ada is building a new restaurant in the following way:
- First, $N$ points $X_1, X_2, \ldots, X_N$ are chosen on the $x$-axis.
- Then, $N$ columns (numbered $1$ through $N$) are made. For simplicity, the columns are represented as vertical segments; for each valid $i$, the height of the $i$-th segment is $H_i$.
- Ada assigns a column to each of the points $X_1, X_2, \ldots, X_N$ in an arbitrary way (each column must be assigned to exactly one point).
- Finally, Ada constructs the roof of the restaurant, represented by a polyline with $N$ vertices. Let's denote the column assigned to the $i$-th point by $P_i$. For each valid $i$, the $i$-th of these vertices is $(X_i, H_{P_i})$, i.e. the polyline joins the tops of the columns from left to right.
Ada wants the biggest restaurant. Help her choose the positions of the columns in such a way that the area below the roof is the biggest possible. Formally, she wants to maximise the area of the polygon whose perimeter is formed by the roof and the segments $(X_N, H_{P_N}) - (X_N, 0) - (X_1, 0) - (X_1, H_{P_1})$. Let $S$ be this maximum area; you should compute $2 \cdot S$ (it is guaranteed that $2 \cdot S$ is an integer).

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $X_i$ and $H_i$.

-----Output-----
For each test case, print a single line containing one integer $2 \cdot S$.

-----Constraints-----
- $1 \le T \le 3 \cdot 10^5$
- $2 \le N \le 10^5$
- $0 \le X_1 < X_2 < \ldots < X_N \le 2 \cdot 10^9$
- $1 \le H_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $10^6$

-----Example Input-----
1
5
1 1
2 2
3 3
4 4
5 5

-----Example Output-----
27

-----Explanation-----

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A weighted string is a string of lowercase English letters where each letter has a weight.  Character weights are $\mbox{1}$ to $26$ from $\class{ML__boldsymbol}{\boldsymbol{a}}$ to $z$ as shown below:

The weight of a string is the sum of the weights of its characters.  For example: 

A uniform string consists of a single character repeated zero or more times. For example, ccc and a are uniform strings, but bcb and cd are not.

Given a string, $\boldsymbol{\mathrm{~S~}}$, let $\mbox{U}$ be the set of weights for all possible uniform contiguous  substrings of string $\boldsymbol{\mathrm{~S~}}$. There will be $n$ queries to answer where each query consists of a single integer. Create a return array where for each query, the value is Yes if $\textit{query}[i]\in U$.  Otherwise, append No.

Note: The  $\in $ symbol denotes that $x[i]$ is an element of set $\mbox{U}$.Example $s=\text{'abbcccddd’}$ $queries=[1,7,5,4,15]$.  
Working from left to right, weights that exist are:
string  weighta     
  1b       2bb     
  4c       3cc      
  6ccc     9
   d       4 
   dd     8
   ddd     12
dddd    16

Now for each value in $queries$, see if it exists in the possible string weights.  The return array is ['Yes', 'No', 'No', 'Yes', 'No'].
Function Description  Complete the weightedUniformStrings function in the editor below. weightedUniformStrings has the following parameter(s): - string s: a string - int queries[n]: an array of integers   
Returns -   string[n]: an array of strings that answer the queries

Input FormatThe first line contains a string $\boldsymbol{\mathrm{~S~}}$, the original string. The second line contains an integer $n$, the number of queries. Each of the next $n$ lines contains an integer $\textit{queries}[i]$, the weight of a uniform subtring of $\boldsymbol{\mathrm{~S~}}$ that may or may not exist.

Constraints
$1\leq\textit{lengthofs},n\leq10^5$       
$1\leq\textit{queries[i]}\leq10^7$
$\boldsymbol{\mathrm{~S~}}$ will only contain lowercase English letters, ascii[a-z].

Sample Input0 
abccddde
6
1
3
12
5
9 
10

Sample Output0
Yes
Yes
Yes
Yes
No
No
Explanation 0
The weights of every possible uniform substring in the string abccddde are shown below:

We print Yes on the first four lines because the first four queries match weights of uniform substrings of $\boldsymbol{\mathrm{~S~}}$. We print No for the last two queries because there are no uniform substrings in $\boldsymbol{\mathrm{~S~}}$ that have those weights. 

Note that while de is a substring of $\boldsymbol{\mathrm{~S~}}$ that would have a weight of $\mbox{9}$, it is not a uniform substring.

 Note that we are only dealing with contiguous substrings. So ccc is not a substring of the string ccxxc.
Sample Input1
aaabbbbcccddd
5
9
7
8
12
5
Sample Output 1
Yes
No
Yes
Yes
No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n casinos lined in a row. If Memory plays at casino i, he has probability pi to win and move to the casino on the right (i + 1) or exit the row (if i = n), and a probability 1 - pi to lose and move to the casino on the left (i - 1) or also exit the row (if i = 1). 

We say that Memory dominates on the interval i... j if he completes a walk such that,

  * He starts on casino i. 
  * He never looses in casino i. 
  * He finishes his walk by winning in casino j. 



Note that Memory can still walk left of the 1-st casino and right of the casino n and that always finishes the process.

Now Memory has some requests, in one of the following forms:

  * 1 i a b: Set <image>. 
  * 2 l r: Print the probability that Memory will dominate on the interval l... r, i.e. compute the probability that Memory will first leave the segment l... r after winning at casino r, if she starts in casino l. 



It is guaranteed that at any moment of time p is a non-decreasing sequence, i.e. pi ≤ pi + 1 for all i from 1 to n - 1.

Please help Memory by answering all his requests!

Input

The first line of the input contains two integers n and q(1 ≤ n, q ≤ 100 000), — number of casinos and number of requests respectively.

The next n lines each contain integers ai and bi (1 ≤ ai < bi ≤ 109) — <image> is the probability pi of winning in casino i.

The next q lines each contain queries of one of the types specified above (1 ≤ a < b ≤ 109, 1 ≤ i ≤ n, 1 ≤ l ≤ r ≤ n).

It's guaranteed that there will be at least one query of type 2, i.e. the output will be non-empty. Additionally, it is guaranteed that p forms a non-decreasing sequence at all times.

Output

Print a real number for every request of type 2 — the probability that boy will "dominate" on that interval. Your answer will be considered correct if its absolute error does not exceed 10 - 4.

Namely: let's assume that one of your answers is a, and the corresponding answer of the jury is b. The checker program will consider your answer correct if |a - b| ≤ 10 - 4.

Example

Input

3 13
1 3
1 2
2 3
2 1 1
2 1 2
2 1 3
2 2 2
2 2 3
2 3 3
1 2 2 3
2 1 1
2 1 2
2 1 3
2 2 2
2 2 3
2 3 3


Output

0.3333333333
0.2000000000
0.1666666667
0.5000000000
0.4000000000
0.6666666667
0.3333333333
0.2500000000
0.2222222222
0.6666666667
0.5714285714
0.6666666667

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n students who have taken part in an olympiad. Now it's time to award the students.

Some of them will receive diplomas, some wiil get certificates, and others won't receive anything. Students with diplomas and certificates are called winners. But there are some rules of counting the number of diplomas and certificates. The number of certificates must be exactly k times greater than the number of diplomas. The number of winners must not be greater than half of the number of all students (i.e. not be greater than half of n). It's possible that there are no winners.

You have to identify the maximum possible number of winners, according to these rules. Also for this case you have to calculate the number of students with diplomas, the number of students with certificates and the number of students who are not winners.


-----Input-----

The first (and the only) line of input contains two integers n and k (1 ≤ n, k ≤ 10^12), where n is the number of students and k is the ratio between the number of certificates and the number of diplomas.


-----Output-----

Output three numbers: the number of students with diplomas, the number of students with certificates and the number of students who are not winners in case when the number of winners is maximum possible.

It's possible that there are no winners.


-----Examples-----
Input
18 2

Output
3 6 9

Input
9 10

Output
0 0 9

Input
1000000000000 5

Output
83333333333 416666666665 500000000002

Input
1000000000000 499999999999

Output
1 499999999999 500000000000

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

The site of Mr. A's house, which lives in a certain city, is surrounded by white walls. Feeling unsatisfied with the wall, Mr. A decided to invite the children in the neighborhood to paint the wall freely. Ask the children to choose their favorite section of the wall and paint it. So how was the wall painted?

Problem

There is a circular white wall as shown below, which consists of sections 0 to N-1.


Figure 1



M children specify the starting position a of this wall and the length L from the starting position, and paint counterclockwise from a to (a + L) mod N (however, a mod N is Represents the remainder when a is divided by N). Here, it is possible to paint over the section painted by another person, in which case it is regarded as one section painted with color. Output the colored sections in descending order. Also, output at the same time how many sections of that size are.

Constrains

Input meets the following conditions

* 2 ≤ N ≤ 100
* 1 ≤ M ≤ 50
* 0 ≤ ai <N
* 1 ≤ Li ≤ N



Input

The input is given in the following format.


N M
a0 L0
a1 L1
...
aM−1 LM−1


The first line is given two integers N, M, separated by blanks, which represent the length of the wall and the number of people who paint the wall, respectively. The following M line is given the start position ai and the length Li of the section to be painted by each person.

Output

The length of the colored section and the total number of the lengths are output in descending order of the colored section.

Examples

Input

5 3
0 1
2 1
3 1


Output

2 1
1 1


Input

4 2
0 2
1 2


Output

3 1


Input

10 3
2 1
4 1
9 2


Output

2 1
1 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The i-th person has weight people[i], and each boat can carry a maximum weight of limit.
Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit.
Return the minimum number of boats to carry every given person.  (It is guaranteed each person can be carried by a boat.)
 

Example 1:
Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)


Example 2:
Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)


Example 3:
Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)
Note:

1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have two consecutive integers k1 and k2, k2 = k1 + 1

We need to calculate the lowest integer `n`, such that:
the values nk1 and nk2 have the same digits but in different order.

E.g.# 1:
```
k1 = 100
k2 = 101
n = 8919
#Because 8919 * 100 = 891900 
and      8919 * 101 = 900819
```

E.g.# 2:
```
k1 = 325
k2 = 326
n = 477
#Because 477 * 325 = 155025
and      477 * 326 = 155502
```

Your task is to prepare a function that will receive the value of `k` and outputs the value of `n`.

The examples given above will be:
```python
find_lowest_int(100) === 8919
find_lowest_int(325) ===  477
```
Features of the random tests
```
10 < k < 10.000.000.000.000.000 (For Python, Ruby and Haskell)
10 < k < 1.000.000.000  (For Javascript 1e9)
```
Enjoy it!!

Ruby and Javascript versions will be released soon.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n schoolchildren, boys and girls, lined up in the school canteen in front of the bun stall. The buns aren't ready yet and the line is undergoing some changes.

Each second all boys that stand right in front of girls, simultaneously swap places with the girls (so that the girls could go closer to the beginning of the line). In other words, if at some time the i-th position has a boy and the (i + 1)-th position has a girl, then in a second, the i-th position will have a girl and the (i + 1)-th one will have a boy.

Let's take an example of a line of four people: a boy, a boy, a girl, a girl (from the beginning to the end of the line). Next second the line will look like that: a boy, a girl, a boy, a girl. Next second it will be a girl, a boy, a girl, a boy. Next second it will be a girl, a girl, a boy, a boy. The line won't change any more.

Your task is: given the arrangement of the children in the line to determine the time needed to move all girls in front of boys (in the example above it takes 3 seconds). Baking buns takes a lot of time, so no one leaves the line until the line stops changing.


-----Input-----

The first line contains a sequence of letters without spaces s_1s_2... s_{n} (1 ≤ n ≤ 10^6), consisting of capital English letters M and F. If letter s_{i} equals M, that means that initially, the line had a boy on the i-th position. If letter s_{i} equals F, then initially the line had a girl on the i-th position.


-----Output-----

Print a single integer — the number of seconds needed to move all the girls in the line in front of the boys. If the line has only boys or only girls, print 0.


-----Examples-----
Input
MFM

Output
1

Input
MMFF

Output
3

Input
FFMMM

Output
0



-----Note-----

In the first test case the sequence of changes looks as follows: MFM  →  FMM.

The second test sample corresponds to the sample from the statement. The sequence of changes is: MMFF  →  MFMF  →  FMFM  →  FFMM.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pero has negotiated a Very Good data plan with his internet provider. The provider will let Pero use up $X$ megabytes to surf the internet per month. Each megabyte that he doesn’t spend in that month gets transferred to the next month and can still be spent. Of course, Pero can only spend the megabytes he actually has.

If we know how much megabytes Pero has spent in each of the first $N$ months of using the plan, determine how many megabytes Pero will have available in the $N + 1$ month of using the plan.

-----Input-----
The first line of input contains the integer $X$ ($1 \leq X \leq 100$). The second line of input contains the integer $N$ ($1 \leq N \leq 100$). Each of the following $N$ lines contains an integer $P_ i$ ($0 \leq P_ i \leq 10000$), the number of megabytes spent in each of the first $N$ months of using the plan. Numbers $P_ i$ will be such that Pero will never use more megabytes than he actually has.

-----Output-----
The first and only line of output must contain the required value from the task.

-----Examples-----
Sample Input 1:
10
3
4
6
2
Sample Output 1:
28

Sample Input 2:
10
3
10
2
12
Sample Output 2:
16

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a non-negative number num in the form of string. The task is to apply at most one swap operation on the number num so that the result is the next higher number.
Example 1:
Input: num = "768"
Output: "786"
Explanation: This is next higher
number that we can get.
Example 2:
Input: num = "333"
Output: "-1"
Explanation: There is no higher
number than 333. 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function nxtHighUsingAtMostOneSwap() which takes the string num as inputs and returns the answer.
Expected Time Complexity: O(|num|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |num| ≤ 10^{5}
|num| denotes the length of the string num.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given $n$ elements numbered from $1$ to $n$, the element $i$ has value $a_i$ and color $c_i$, initially, $c_i = 0$ for all $i$.

The following operation can be applied:

Select three elements $i$, $j$ and $k$ ($1 \leq i < j < k \leq n$), such that $c_i$, $c_j$ and $c_k$ are all equal to $0$ and $a_i = a_k$, then set $c_j = 1$.

Find the maximum value of $\sum\limits_{i=1}^n{c_i}$ that can be obtained after applying the given operation any number of times.


-----Input-----

The first line contains an integer $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the number of elements.

The second line consists of $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$), where $a_i$ is the value of the $i$-th element.


-----Output-----

Print a single integer in a line — the maximum value of $\sum\limits_{i=1}^n{c_i}$ that can be obtained after applying the given operation any number of times.


-----Examples-----

Input
7
1 2 1 2 7 4 7
Output
2
Input
13
1 2 3 2 1 3 3 4 5 5 5 4 7
Output
7


-----Note-----

In the first test, it is possible to apply the following operations in order:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day you and GTmac walk into a classroom and see a mysterious expression on the blackboard:\[ (1^b + 2^b + \cdots + a^b)~ \mathrm{mod}~ a \]

Upon seeing the expression GTmac shows an evil smile and challenges you: “Let me give you the values of $a$ and $b$ and let’s assume $b$ is an odd number. Want to bet who can evaluate this expression? The one who loses shall buy pizza for us tonight.”

-----Input-----
The input has two integers $a$ ($1 \leq a \leq 10^9$) and $b$ ($1\leq b\leq 99$, $b$ is odd) on a single line.

-----Output-----
Output the value of the expression with the given $a$ and $b$.

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

Sample Input 2:
3 7
Sample Output 2:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S, remove all consonants and print the modified string that contains vowels only.
Example 1:
Input
S = "abEkipo"
Output
aEio
Explanation : a, E, i, o are only vowels in the string.
Example 2:
Input
S = "rrty"
Output
No Vowel
Explanation: There are no vowels.
Your Task: You don't need to read input or print anything.Your task is to complete the function removeConsonants() which takes a string as input parameters, and returns the modified string that contains vowels only. If there is no vowel present in the string S, then return "No Vowel".
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(1).
Constraints
1 <= |S| <= 10^{5}
The string should consist of only alphabets.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive integer $m$ and two integer sequence: $a=[a_1, a_2, \ldots, a_n]$ and $b=[b_1, b_2, \ldots, b_n]$. Both of these sequence have a length $n$.

Permutation is a sequence of $n$ different positive integers from $1$ to $n$. For example, these sequences are permutations: $[1]$, $[1,2]$, $[2,1]$, $[6,7,3,4,1,2,5]$. These are not: $[0]$, $[1,1]$, $[2,3]$.

You need to find the non-negative integer $x$, and increase all elements of $a_i$ by $x$, modulo $m$ (i.e. you want to change $a_i$ to $(a_i + x) \bmod m$), so it would be possible to rearrange elements of $a$ to make it equal $b$, among them you need to find the smallest possible $x$.

In other words, you need to find the smallest non-negative integer $x$, for which it is possible to find some permutation $p=[p_1, p_2, \ldots, p_n]$, such that for all $1 \leq i \leq n$, $(a_i + x) \bmod m = b_{p_i}$, where $y \bmod m$ — remainder of division of $y$ by $m$.

For example, if $m=3$, $a = [0, 0, 2, 1], b = [2, 0, 1, 1]$, you can choose $x=1$, and $a$ will be equal to $[1, 1, 0, 2]$ and you can rearrange it to make it equal $[2, 0, 1, 1]$, which is equal to $b$.


-----Input-----

The first line contains two integers $n,m$ ($1 \leq n \leq 2000, 1 \leq m \leq 10^9$): number of elemens in arrays and $m$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i < m$).

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($0 \leq b_i < m$).

It is guaranteed that there exists some non-negative integer $x$, such that it would be possible to find some permutation $p_1, p_2, \ldots, p_n$ such that $(a_i + x) \bmod m = b_{p_i}$.


-----Output-----

Print one integer, the smallest non-negative integer $x$, such that it would be possible to find some permutation $p_1, p_2, \ldots, p_n$ such that $(a_i + x) \bmod m = b_{p_i}$ for all $1 \leq i \leq n$.


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

Output
1

Input
3 2
0 0 0
1 1 1

Output
1

Input
5 10
0 0 0 1 2
2 1 0 0 0

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi loves palindromes. Non-palindromic strings are unacceptable to him. Each time he hugs a string, he can change one of its characters to any character of his choice.
Given is a string S. Find the minimum number of hugs needed to make S palindromic.

-----Constraints-----
 - S is a string consisting of lowercase English letters.
 - The length of S is between 1 and 100 (inclusive).

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

-----Output-----
Print the minimum number of hugs needed to make S palindromic.

-----Sample Input-----
redcoder

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

For example, we can change the fourth character to o and get a palindrome redooder.

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