vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are given an array arr  of length N of 0's and 1's. Find the total number of subarrays of 0's
Example 1:
Input:
N = 4
arr[] = {0, 0, 1, 0}
Output:
4
Explanation:
Following are the subarrays of
length 1: {0}, {0}, {0} - 3
length 2: {0, 0} - 1
Total Subarrays: 3 + 1 = 4
Example 2:
Input:
N = 4
arr[] = {0, 0, 0, 0}
Output:
10
Explanation:
Following are the subarrays of
length 1: {0}, {0}, {0}, {0} - 4
length 2: {0, 0}, {0, 0}, {0, 0} - 3
length 3: {0, 0, 0}, {0, 0, 0} - 2
length 4: {0, 0, 0, 0} - 1
Total Subarrays: 4 + 3 + 2 + 1 = 10
Your Task:
Your task is to complete the function no_of_subarrays(), which takes an integer N and an integer array arr as the input parameters and returns an integer denoting the total number of subarrays of 0's.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
	1 <= N <= 10^{6}
	0 <= arr[i] <= 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Everyone loves short problem statements.
Given a function $ f(x) $ find its minimum value over the range $ 0 < x < π/2$
$
f(x) = ( x^2 + b*x + c ) / sin( x )
$

-----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 real numbers $b, c$. 

-----Output:-----
For each test case, output the minimum value of $ f(x) $ over the given range. Absolute error of $10^{-6}$ is allowed.

-----Constraints-----
- $1 \leq T \leq 100000$
- $1 \leq b,c \leq 20$

-----Sample Input:-----
1
2 2

-----Sample Output:-----
5.8831725615

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 In a black and white image we can use `1` instead of black pixels and `0` instead of white pixels. 
 
 For compression image file we can reserve pixels by consecutive pixels who have the same color. 
 
 Your task is to determine how much of black and white pixels is in each row sorted by place of those.
 
# Example:

 For `height=2,width=100 and compressed=[40,120,40,0]`

 The result should be `[[40,60],[0,60,40,0]]`
 
 Sum of compressed array always divisible by width and height of image.
 
 Pixels available is in Compressed array in this order:
 
 `[Black,White,Black,White,Black,White,...]`
 
 ![](http://s3.picofile.com/file/8194350650/Compressed_Image_1_.png)

 For `height=2,width=100 and compressed=[0, 180, 20, 0]`

 The result should be `[[0,100],[0,80,20,0]]`

 ![](http://s6.picofile.com/file/8194348868/Compressed_Image.png)


# Input/Output


- `[input]` integer `height`

  Height of image


- `[input]` integer `width`

  Width of image


- `[input]` integer array `compressed`

  Consecutive pixels


- `[output]` 2D integer array

 The black and white pixels in each row.

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

Number pyramid is a recursive structure where each next row is constructed by adding adjacent values of the current row. For example:

```
Row 1     [1     2     3     4]
Row 2        [3     5     7]
Row 3           [8    12]
Row 4             [20]
```

___

## Task

Given the first row of the number pyramid, find the value stored in its last row.

___

## Examples

```python
reduce_pyramid([1])        ==  1
reduce_pyramid([3, 5])     ==  8
reduce_pyramid([3, 9, 4])  ==  25
```

___

## Performance tests

```python
Number of tests: 10
List size: 10,000
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given that a mango weighs X kilograms and a truck weighs Y kilograms.
You want to cross a bridge that can withstand a weight of Z kilograms. 

Find the maximum number of mangoes you can load in the truck so that you can cross the bridge safely.

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

- First line will contain T, the number of test cases. Then the test cases follow.
- Each test case consists of a single line of input, three integers X, Y, Z - the weight of mango, the weight of truck and the weight the bridge can withstand respectively.

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

For each test case, output in a single line the maximum number of mangoes that you can load in the truck.

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

$1 ≤ T ≤ 1000$
$1 ≤ X ≤ Y ≤ Z ≤ 100$

----- Sample Input 1 ------ 
4
2 5 11
4 10 20
1 1 1
6 40 90

----- Sample Output 1 ------ 
3
2
0
8

----- explanation 1 ------ 
Test case $1$: You can load $3$ mangoes at maximum. The total weight is $ 3\times 2+5 = 11 ≤ 11$. Thus, the truck can safely cross the bridge with $3$ mangoes. If you load $4$ mangoes, the total weight is $4\times 2+5 = 13 > 11$. 

Test case $2$: You can load $2$ mangoes at maximum. The total weight is $ 2\times 4+10 = 18 ≤ 20$. Thus, the truck can safely cross the bridge with $2$ mangoes.

Test case $3$: You can load $0$ mangoes at maximum. The total weight is $ 0\times 1+1 = 1 ≤ 1$. Thus, the truck can safely cross the bridge only if there are $0$ mangoes.

Test case $4$: You can load $8$ mangoes at maximum. The total weight is $ 6\times 8+40 = 88 ≤ 90$. Thus, the truck can safely cross the bridge with $8$ mangoes.

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

Your job here is to implement a function `factors`, which takes a number `n`, and outputs an array of arrays comprised of two
parts, `sq` and `cb`. The part `sq` will contain all the numbers that, when squared, yield a number which is a factor of `n`,
while the `cb` part will contain all the numbers that, when cubed, yield a number which is a factor of `n`.  Discard all `1`s
from both arrays.

Both `sq` and `cb` should be sorted in ascending order.

#### What it looks like:

```python
factors(int) #=> [
  sq (all the numbers that can be squared to give a factor of n) : list,
  cb (all the numbers that can be cubed   to give a factor of n) : list
]
```

#### Some examples:

Also check out my other creations — [Keep the Order](https://www.codewars.com/kata/keep-the-order), [Naming Files](https://www.codewars.com/kata/naming-files), [Elections: Weighted Average](https://www.codewars.com/kata/elections-weighted-average), [Identify Case](https://www.codewars.com/kata/identify-case), [Split Without Loss](https://www.codewars.com/kata/split-without-loss), [Adding Fractions](https://www.codewars.com/kata/adding-fractions),
[Random Integers](https://www.codewars.com/kata/random-integers), [Implement String#transpose](https://www.codewars.com/kata/implement-string-number-transpose), [Implement Array#transpose!](https://www.codewars.com/kata/implement-array-number-transpose), [Arrays and Procs #1](https://www.codewars.com/kata/arrays-and-procs-number-1), and [Arrays and Procs #2](https://www.codewars.com/kata/arrays-and-procs-number-2).

If you notice any issues or have any suggestions/comments whatsoever, please don't hesitate to mark an issue or just comment. Thanks!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a sorted and rotated array A of N distinct elements which is rotated at some point, and given an element key. The task is to find the index of the given element key in the array A. The whole array A is given as the range to search.
Example 1:
Input:
N = 9
A[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}
key = 10
l = 0 , h = 8
Output:
5
Explanation: 10 is found at index 5.
Example 2:
Input:
N = 4
A[] = {3, 5, 1, 2}
key = 6
l = 0 , h = 3
Output:
-1
Explanation: There is no element that has value 6.
Your Task:
Complete the function search() which takes an array arr[] and start, end index of the array and the K as input parameters, and returns the answer.
Can you solve it in expected time complexity?
Expected Time Complexity: O(log N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{7}
0 ≤ A[i] ≤ 10^{8}
1 ≤ key ≤ 10^{8}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This problem is different from the easy version. In this version Ujan makes at most 2n swaps. In addition, k ≤ 1000, n ≤ 50 and it is necessary to print swaps themselves. You can hack this problem if you solve it. But you can hack the previous problem only if you solve both problems.

After struggling and failing many times, Ujan decided to try to clean up his house again. He decided to get his strings in order first.

Ujan has two distinct strings s and t of length n consisting of only of lowercase English characters. He wants to make them equal. Since Ujan is lazy, he will perform the following operation at most 2n times: he takes two positions i and j (1 ≤ i,j ≤ n, the values i and j can be equal or different), and swaps the characters s_i and t_j.

Ujan's goal is to make the strings s and t equal. He does not need to minimize the number of performed operations: any sequence of operations of length 2n or shorter is suitable.

Input

The first line contains a single integer k (1 ≤ k ≤ 1000), the number of test cases.

For each of the test cases, the first line contains a single integer n (2 ≤ n ≤ 50), the length of the strings s and t. 

Each of the next two lines contains the strings s and t, each having length exactly n. The strings consist only of lowercase English letters. It is guaranteed that strings are different.

Output

For each test case, output "Yes" if Ujan can make the two strings equal with at most 2n operations and "No" otherwise. You can print each letter in any case (upper or lower).

In the case of "Yes" print m (1 ≤ m ≤ 2n) on the next line, where m is the number of swap operations to make the strings equal. Then print m lines, each line should contain two integers i, j (1 ≤ i, j ≤ n) meaning that Ujan swaps s_i and t_j during the corresponding operation. You do not need to minimize the number of operations. Any sequence of length not more than 2n is suitable.

Example

Input


4
5
souse
houhe
3
cat
dog
2
aa
az
3
abc
bca


Output


Yes
1
1 4
No
No
Yes
3
1 2
3 1
2 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This problem has nothing to do with Little Chris. It is about hill climbers instead (and Chris definitely isn't one).

There are n hills arranged on a line, each in the form of a vertical line segment with one endpoint on the ground. The hills are numbered with numbers from 1 to n from left to right. The i-th hill stands at position xi with its top at height yi. For every two hills a and b, if the top of hill a can be seen from the top of hill b, their tops are connected by a rope. Formally, the tops of two hills are connected if the segment connecting their top points does not intersect or touch any of the other hill segments. Using these ropes, the hill climbers can move from hill to hill.

There are m teams of climbers, each composed of exactly two members. The first and the second climbers of the i-th team are located at the top of the ai-th and bi-th hills, respectively. They want to meet together at the top of some hill. Now, each of two climbers move according to the following process:

  1. if a climber is at the top of the hill where the other climber is already located or will come eventually, the former climber stays at this hill; 
  2. otherwise, the climber picks a hill to the right of his current hill that is reachable by a rope and is the rightmost possible, climbs this hill and continues the process (the climber can also climb a hill whose top is lower than the top of his current hill). 

<image>

For each team of climbers, determine the number of the meeting hill for this pair!

Input

The first line of input contains a single integer n (1 ≤ n ≤ 105), the number of hills. The next n lines describe the hills. The i-th of them contains two space-separated integers xi, yi (1 ≤ xi ≤ 107; 1 ≤ yi ≤ 1011), the position and the height of the i-th hill. The hills are given in the ascending order of xi, i.e., xi < xj for i < j.

The next line of input contains a single integer m (1 ≤ m ≤ 105), the number of teams. The next m lines describe the teams. The i-th of them contains two space-separated integers ai, bi (1 ≤ ai, bi ≤ n), the numbers of the hills where the climbers of the i-th team are located. It is possible that ai = bi.

Output

In a single line output m space-separated integers, where the i-th integer is the number of the meeting hill for the members of the i-th team.

Examples

Input

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


Output

5 6 3 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya is sitting on an extremely boring math class. To have fun, he took a piece of paper and wrote out n numbers on a single line. After that, Vasya began to write out different ways to put pluses ("+") in the line between certain digits in the line so that the result was a correct arithmetic expression; formally, no two pluses in such a partition can stand together (between any two adjacent pluses there must be at least one digit), and no plus can stand at the beginning or the end of a line. For example, in the string 100500, ways 100500 (add no pluses), 1+00+500 or 10050+0 are correct, and ways 100++500, +1+0+0+5+0+0 or 100500+ are incorrect.

The lesson was long, and Vasya has written all the correct ways to place exactly k pluses in a string of digits. At this point, he got caught having fun by a teacher and he was given the task to calculate the sum of all the resulting arithmetic expressions by the end of the lesson (when calculating the value of an expression the leading zeros should be ignored). As the answer can be large, Vasya is allowed to get only its remainder modulo 10^9 + 7. Help him!


-----Input-----

The first line contains two integers, n and k (0 ≤ k < n ≤ 10^5).

The second line contains a string consisting of n digits.


-----Output-----

Print the answer to the problem modulo 10^9 + 7.


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

Output
27
Input
3 2
108

Output
9


-----Note-----

In the first sample the result equals (1 + 08) + (10 + 8) = 27.

In the second sample the result equals 1 + 0 + 8 = 9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Some time ago Lesha found an entertaining string $s$ consisting of lowercase English letters. Lesha immediately developed an unique algorithm for this string and shared it with you. The algorithm is as follows.

Lesha chooses an arbitrary (possibly zero) number of pairs on positions $(i, i + 1)$ in such a way that the following conditions are satisfied:   for each pair $(i, i + 1)$ the inequality $0 \le i < |s| - 1$ holds;  for each pair $(i, i + 1)$ the equality $s_i = s_{i + 1}$ holds;  there is no index that is contained in more than one pair.  After that Lesha removes all characters on indexes contained in these pairs and the algorithm is over. 

Lesha is interested in the lexicographically smallest strings he can obtain by applying the algorithm to the suffixes of the given string.


-----Input-----

The only line contains the string $s$ ($1 \le |s| \le 10^5$) — the initial string consisting of lowercase English letters only.


-----Output-----

In $|s|$ lines print the lengths of the answers and the answers themselves, starting with the answer for the longest suffix. The output can be large, so, when some answer is longer than $10$ characters, instead print the first $5$ characters, then "...", then the last $2$ characters of the answer.


-----Examples-----
Input
abcdd

Output
3 abc
2 bc
1 c
0 
1 d

Input
abbcdddeaaffdfouurtytwoo

Output
18 abbcd...tw
17 bbcdd...tw
16 bcddd...tw
15 cddde...tw
14 dddea...tw
13 ddeaa...tw
12 deaad...tw
11 eaadf...tw
10 aadfortytw
9 adfortytw
8 dfortytw
9 fdfortytw
8 dfortytw
7 fortytw
6 ortytw
5 rtytw
6 urtytw
5 rtytw
4 tytw
3 ytw
2 tw
1 w
0 
1 o



-----Note-----

Consider the first example.

  The longest suffix is the whole string "abcdd". Choosing one pair $(4, 5)$, Lesha obtains "abc".  The next longest suffix is "bcdd". Choosing one pair $(3, 4)$, we obtain "bc".  The next longest suffix is "cdd". Choosing one pair $(2, 3)$, we obtain "c".  The next longest suffix is "dd". Choosing one pair $(1, 2)$, we obtain "" (an empty string).  The last suffix is the string "d". No pair can be chosen, so the answer is "d". 

In the second example, for the longest suffix "abbcdddeaaffdfouurtytwoo" choose three pairs $(11, 12)$, $(16, 17)$, $(23, 24)$ and we obtain "abbcdddeaadfortytw"

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

A dolphin who lives in a certain aquarium will be rewarded if he jumps and goes through the $ N $ ring.

* Dolphin jumps from coordinates $ (0,0) $ and lands at $ (T,0) $.
* The trajectory of the jump is a parabola.
* The $ i $ th ring is determined to have passed through when the jump trajectory intersects the line segment connecting $ (X_i, L_i) $ and $ (X_i, H_i) $.
* $ 1 $ jump requires as much physical strength as the initial velocity.



Dolphins can jump as many times as they want. Let the gravitational acceleration vector be $ (0, -1) $ and find the minimum total physical strength required for the dolphin to pass through all the rings. However, suppose friction and air resistance are negligibly small.

Constraints

The input satisfies the following conditions.

* All inputs are integers.
* $ 1 \ le X_i <T \ le 10 ^ 6 $
* $ 1 \ le N \ le 10 ^ 5 $
* $ 1 \ le L_i <H_i \ le 10 ^ 6 $

Input

The input is given in the following format.


$ T $ $ N $
$ X_1 $ $ L_1 $ $ H_1 $
$ \ vdots $
$ X_N $ $ L_N $ $ H_N $


First, $ T $ and $ N $ are given to the $ 1 $ line. Then the $ N $ line is given the position of the $ i $ th ring, $ X_i $, $ L_i $, and $ H_i $.

Output

Output the answer on one line. If the absolute error or relative error is $ 10 ^ {-9} $ or less, the answer is judged to be correct.

Examples

Input

100 5
50 1 5
50 5 10
50 20 30
50 40 60
50 61 1000000


Output

48.6090201099


Input

64 15
38 133177 927361
48 177920 668766
12 680425 790550
43 6853 384115
17 214954 723798
62 63843 153825
28 399349 482937
2 336136 367001
33 138008 733496
6 203462 911631
58 321974 527734
17 696940 781678
55 265874 507640
41 56037 880001
34 279422 528651


Output

6087.909851326286

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a square matrix of size N×N, calculate the absolute difference between the sums of its diagonals. 

-----Input-----
The first line contains a single integer N. The next N lines denote the matrix's rows, with each line containing N space-separated integers describing the columns.

-----Output-----
Print the absolute difference between the two sums of the matrix's diagonals as a single integer.

-----Constraints-----
1<=N<=10

-----Example-----
Input:
3
11 2 4
4 5 6
10 8 -12

Output:
15

-----Explanation-----
The primary diagonal is: 
11
5
-12
Sum across the primary diagonal: 11 + 5 - 12 = 4
The secondary diagonal is:
4
5
10
Sum across the secondary diagonal: 4 + 5 + 10 = 19 
Difference: |4 - 19| = 15

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two integers N$N$ and M$M$. You have to construct a matrix with N$N$ rows and M$M$ columns. Consider a multiset S$S$ which contains N+M$N + M$ integers: for each row and each column of this matrix, the MEX of the elements of this row/column belongs to S$S$. Then, in the matrix you construct, the MEX of S$S$ must be maximum possible. 
Note: The MEX of a multiset of integers is the smallest non-negative integer that is not present in this multiset. For example, MEX({4,9,0,1,1,5})=2$\mathrm{MEX}(\{4,9,0,1,1,5\}) = 2$ and MEX({1,2,3})=0$\mathrm{MEX}(\{1,2,3\}) = 0$.

-----Input-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
- The first and only line of each test case contains two space-separated integers N$N$ and M$M$.

-----Output-----
For each test case, print N$N$ lines. For each i$i$ (1≤i≤N$1 \le i \le N$), the i$i$-th of these lines should contain M$M$ space-separated integers ― the elements in the i$i$-th row of your matrix. Each element of the matrix must be non-negative and must not exceed 109$10^9$.
If there are multiple solutions, you may find any one of them.

-----Constraints-----
- 1≤T≤400$1 \le T \le 400$
- 1≤N,M≤100$1 \le N, M \le 100$
- the sum of N⋅M$N \cdot M$ over all test cases does not exceed 105$10^5$

-----Example Input-----
2
3 3
4 2

-----Example Output-----
9 1 0
1 0 2
7 5 8
2 2
3 0
1 1
0 1

-----Explanation-----
Example case 1: The MEXs of the rows {9,1,0}$\{9, 1, 0\}$, {1,0,2}$\{1, 0, 2\}$ and {7,5,8}$\{7, 5, 8\}$ are 2$2$, 3$3$ and 0$0$ respectively. The MEXs of the columns {9,1,7}$\{9, 1, 7\}$, {1,0,5}$\{1, 0, 5\}$ and {0,2,8}$\{0, 2, 8\}$ are 0$0$, 2$2$ and 1$1$ respectively. Therefore, the multiset which contains the MEX of each row and each column is S={0,0,1,2,2,3}$S = \{0, 0, 1, 2, 2, 3\}$ and MEX(S)=4$\mathrm{MEX}(S) = 4$. We can show that this is the largest MEX that can be obtained for a 3×3$3 \times 3$ matrix.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
User ainta has a permutation p_1, p_2, ..., p_{n}. As the New Year is coming, he wants to make his permutation as pretty as possible.

Permutation a_1, a_2, ..., a_{n} is prettier than permutation b_1, b_2, ..., b_{n}, if and only if there exists an integer k (1 ≤ k ≤ n) where a_1 = b_1, a_2 = b_2, ..., a_{k} - 1 = b_{k} - 1 and a_{k} < b_{k} all holds.

As known, permutation p is so sensitive that it could be only modified by swapping two distinct elements. But swapping two elements is harder than you think. Given an n × n binary matrix A, user ainta can swap the values of p_{i} and p_{j} (1 ≤ i, j ≤ n, i ≠ j) if and only if A_{i}, j = 1.

Given the permutation p and the matrix A, user ainta wants to know the prettiest permutation that he can obtain.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 300) — the size of the permutation p.

The second line contains n space-separated integers p_1, p_2, ..., p_{n} — the permutation p that user ainta has. Each integer between 1 and n occurs exactly once in the given permutation.

Next n lines describe the matrix A. The i-th line contains n characters '0' or '1' and describes the i-th row of A. The j-th character of the i-th line A_{i}, j is the element on the intersection of the i-th row and the j-th column of A. It is guaranteed that, for all integers i, j where 1 ≤ i < j ≤ n, A_{i}, j = A_{j}, i holds. Also, for all integers i where 1 ≤ i ≤ n, A_{i}, i = 0 holds.


-----Output-----

In the first and only line, print n space-separated integers, describing the prettiest permutation that can be obtained.


-----Examples-----
Input
7
5 2 4 3 6 7 1
0001001
0000000
0000010
1000001
0000000
0010000
1001000

Output
1 2 4 3 6 7 5

Input
5
4 2 1 5 3
00100
00011
10010
01101
01010

Output
1 2 3 4 5



-----Note-----

In the first sample, the swap needed to obtain the prettiest permutation is: (p_1, p_7).

In the second sample, the swaps needed to obtain the prettiest permutation is (p_1, p_3), (p_4, p_5), (p_3, p_4).  [Image] 

A permutation p is a sequence of integers p_1, p_2, ..., p_{n}, consisting of n distinct positive integers, each of them doesn't exceed n. The i-th element of the permutation p is denoted as p_{i}. The size of the permutation p is denoted as n.

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