vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
# Task
 Given an array `arr`, find the rank of the element at the ith position.

 The `rank` of the arr[i] is a value equal to the number of elements `less than or equal to` arr[i] standing before arr[i], plus the number of elements `less than` arr[i] standing after arr[i].

# Example

 For `arr = [2,1,2,1,2], i = 2`, the result should be `3`.
 
 There are 2 elements `less than or equal to` arr[2] standing before arr[2]: 
 
 `arr[0] <= arr[2]`
 
 `arr[1] <= arr[2]`
 
 There is only 1 element `less than` arr[2] standing after arr[2]: 
 
 `arr[3] < arr[2]`
 
 So the result is `2 + 1 = 3`.
 
# Input/Output


 - `[input]` integer array `arr`

  An array of integers.

  `3 <= arr.length <= 50.`


 - `[input]` integer `i`

  Index of the element whose rank is to be found.

  
 - `[output]` an integer

  Rank of the element at the ith position.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Hey You !

Sort these integers for me ...

By name ...

Do it now !


---

## Input

* Range is ```0```-```999```

* There may be duplicates

* The array may be empty

## Example

* Input: 1, 2, 3, 4
* Equivalent names: "one", "two", "three", "four"
* Sorted by name: "four", "one", "three", "two"
* Output: 4, 1, 3, 2

## Notes
* Don't pack words together:
 * e.g. 99 may be "ninety nine" or "ninety-nine"; but not "ninetynine"
 * e.g 101 may be "one hundred one" or "one hundred and one"; but not "onehundredone"
* Don't fret about formatting rules, because if rules are consistently applied it has no effect anyway:
 * e.g. "one hundred one", "one hundred two"; is same order as "one hundred **and** one", "one hundred **and** two"
 * e.g. "ninety eight", "ninety nine"; is same order as "ninety-eight", "ninety-nine"
 
```if:c
* For `C` code the input array may be NULL. The return value is freed if non-NULL.
```

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an image, that can be represented with a 2-d *n* by *m* grid of pixels. Each pixel of the image is either on or off, denoted by the characters "0" or "1", respectively. You would like to compress this image. You want to choose an integer *k*<=&gt;<=1 and split the image into *k* by *k* blocks. If *n* and *m* are not divisible by *k*, the image is padded with only zeros on the right and bottom so that they are divisible by *k*. Each pixel in each individual block must have the same value. The given image may not be compressible in its current state. Find the minimum number of pixels you need to toggle (after padding) in order for the image to be compressible for some *k*. More specifically, the steps are to first choose *k*, then the image is padded with zeros, then, we can toggle the pixels so it is compressible for this *k*. The image must be compressible in that state.

Input Specification:
The first line of input will contain two integers *n*,<=*m* (2<=≤<=*n*,<=*m*<=≤<=2<=500), the dimensions of the image.

The next *n* lines of input will contain a binary string with exactly *m* characters, representing the image.

Output Specification:
Print a single integer, the minimum number of pixels needed to toggle to make the image compressible.

Demo Input:
['3 5\n00100\n10110\n11001\n']

Demo Output:
['5\n']

Note:
We first choose *k* = 2.

The image is padded as follows: 

We can toggle the image to look as follows: 

We can see that this image is compressible for *k* = 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it.
Return the number of nice sub-arrays.
 
Example 1:
Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

Example 2:
Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There is no odd numbers in the array.

Example 3:
Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16

 
Constraints:

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It has been truly said that love is not meant for everyone.

Let me introduce you to a very sad story of my friend Broken Amit. Yes several times he has been left heartbroken. Looking at his poor condition even God is pity on him. God has given Amit a very nice opportunity to Kiss as many girls as he likes . 

There are N number of girls each having a "Love value" as well as a decrement value. 
So, Amit needs to kiss all the N girls exactly once in some order.
 In one step, he can kiss only a single girl and after every step girl's "Love value" decreases by an amount equal to her decrement value times her index (indexing starts from 0) .  But once a girl has been kissed her "Love value" won't decrease in further steps. 

"Love value" for Amit in a particular step is equal to the sum of "Love values" of all the n girls before the beginning of that step, whereas the "Gross Love Value" of Broken Amit is sum of  "Love Values" for Amit in each step. 

Now Amit not being a good analyzer wants your help to find the maximum "Gross Love Value" he can earn.
Input

First line contains an integer N - denoting the number of girls.

Second line contains N integers denoting the initial "Love value" of the girls (L[i]).

Third line contains N integers denoting the "decrement value of the girls (D[i]).
Output

Single integer denoting maximum "Gross Love Value", Broken Amit can earn.
Constraints

1 ≤ n ≤ 17

0 ≤ L[i] < 500000

0 ≤ D[i] < 500000

SAMPLE INPUT
2
2 4
1 2

SAMPLE OUTPUT
12

Explanation

If Amit kisses the first girl and then the 2nd one -
1st step - 2 + 4 = 6
2nd step - 2 + (4 - 12) = 4
Gross Love Value - 6+4 = 10
If Amit kisses the 2nd girl than the 1st one. 
1st step - 2 + 4 = 6
2nd step - (2 - 01) + 4 = 6
Gross Love Value = 12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array consisting of n non-negative integers a_1, a_2, ..., a_{n}.

You are going to destroy integers in the array one by one. Thus, you are given the permutation of integers from 1 to n defining the order elements of the array are destroyed.

After each element is destroyed you have to find out the segment of the array, such that it contains no destroyed elements and the sum of its elements is maximum possible. The sum of elements in the empty segment is considered to be 0.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — the length of the array.

The second line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9). 

The third line contains a permutation of integers from 1 to n — the order used to destroy elements.


-----Output-----

Print n lines. The i-th line should contain a single integer — the maximum possible sum of elements on the segment containing no destroyed elements, after first i operations are performed.


-----Examples-----
Input
4
1 3 2 5
3 4 1 2

Output
5
4
3
0

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

Output
6
5
5
1
0

Input
8
5 5 4 4 6 6 5 5
5 2 8 7 1 3 4 6

Output
18
16
11
8
8
6
6
0



-----Note-----

Consider the first sample:   Third element is destroyed. Array is now 1 3  *  5. Segment with maximum sum 5 consists of one integer 5.  Fourth element is destroyed. Array is now 1 3  *   * . Segment with maximum sum 4 consists of two integers 1 3.  First element is destroyed. Array is now  *  3  *   * . Segment with maximum sum 3 consists of one integer 3.  Last element is destroyed. At this moment there are no valid nonempty segments left in this array, so the answer is equal to 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between easy and hard versions is the length of the string. You can hack this problem if you solve it. But you can hack the previous problem only if you solve both problems.

Kirk has a binary string $s$ (a string which consists of zeroes and ones) of length $n$ and he is asking you to find a binary string $t$ of the same length which satisfies the following conditions: For any $l$ and $r$ ($1 \leq l \leq r \leq n$) the length of the longest non-decreasing subsequence of the substring $s_{l}s_{l+1} \ldots s_{r}$ is equal to the length of the longest non-decreasing subsequence of the substring $t_{l}t_{l+1} \ldots t_{r}$; The number of zeroes in $t$ is the maximum possible.

A non-decreasing subsequence of a string $p$ is a sequence of indices $i_1, i_2, \ldots, i_k$ such that $i_1 < i_2 < \ldots < i_k$ and $p_{i_1} \leq p_{i_2} \leq \ldots \leq p_{i_k}$. The length of the subsequence is $k$.

If there are multiple substrings which satisfy the conditions, output any.


-----Input-----

The first line contains a binary string of length not more than $10^5$.


-----Output-----

Output a binary string which satisfied the above conditions. If there are many such strings, output any of them.


-----Examples-----
Input
110

Output
010

Input
010

Output
010

Input
0001111

Output
0000000

Input
0111001100111011101000

Output
0011001100001011101000



-----Note-----

In the first example:  For the substrings of the length $1$ the length of the longest non-decreasing subsequnce is $1$;  For $l = 1, r = 2$ the longest non-decreasing subsequnce of the substring $s_{1}s_{2}$ is $11$ and the longest non-decreasing subsequnce of the substring $t_{1}t_{2}$ is $01$;  For $l = 1, r = 3$ the longest non-decreasing subsequnce of the substring $s_{1}s_{3}$ is $11$ and the longest non-decreasing subsequnce of the substring $t_{1}t_{3}$ is $00$;  For $l = 2, r = 3$ the longest non-decreasing subsequnce of the substring $s_{2}s_{3}$ is $1$ and the longest non-decreasing subsequnce of the substring $t_{2}t_{3}$ is $1$; 

The second example is similar to the first one.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Artsem has a friend Saunders from University of Chicago. Saunders presented him with the following problem.

Let [n] denote the set {1, ..., n}. We will also write f: [x] → [y] when a function f is defined in integer points 1, ..., x, and all its values are integers from 1 to y.

Now then, you are given a function f: [n] → [n]. Your task is to find a positive integer m, and two functions g: [n] → [m], h: [m] → [n], such that g(h(x)) = x for all <image>, and h(g(x)) = f(x) for all <image>, or determine that finding these is impossible.

Input

The first line contains an integer n (1 ≤ n ≤ 105).

The second line contains n space-separated integers — values f(1), ..., f(n) (1 ≤ f(i) ≤ n).

Output

If there is no answer, print one integer -1.

Otherwise, on the first line print the number m (1 ≤ m ≤ 106). On the second line print n numbers g(1), ..., g(n). On the third line print m numbers h(1), ..., h(m).

If there are several correct answers, you may output any of them. It is guaranteed that if a valid answer exists, then there is an answer satisfying the above restrictions.

Examples

Input

3
1 2 3


Output

3
1 2 3
1 2 3


Input

3
2 2 2


Output

1
1 1 1
2


Input

2
2 1


Output

-1

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a connected undirected graph with *n* vertices and *m* edges. The vertices are enumerated from 1 to *n*. 

You are given *n* integers *c*1,<=*c*2,<=...,<=*c**n*, each of them is between <=-<=*n* and *n*, inclusive. It is also guaranteed that the parity of *c**v* equals the parity of degree of vertex *v*. The degree of a vertex is the number of edges connected to it.

You are to write a weight between <=-<=2·*n*2 and 2·*n*2 (inclusive) on each edge in such a way, that for each vertex *v* the sum of weights on edges connected to this vertex is equal to *c**v*, or determine that this is impossible.

Input Specification:
The first line contains two integers *n* and *m* (2<=≤<=*n*<=≤<=105, *n*<=-<=1<=≤<=*m*<=≤<=105) — the number of vertices and the number of edges.

The next line contains *n* integers *c*1,<=*c*2,<=...,<=*c**n* (<=-<=*n*<=≤<=*c**i*<=≤<=*n*), where *c**i* is the required sum of weights of edges connected to vertex *i*. It is guaranteed that the parity of *c**i* equals the parity of degree of vertex *i*.

The next *m* lines describe edges of the graph. The *i*-th of these lines contains two integers *a**i* and *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*; *a**i*<=≠<=*b**i*), meaning that the *i*-th edge connects vertices *a**i* and *b**i*.

It is guaranteed that the given graph is connected and does not contain loops and multiple edges.

Output Specification:
If there is no solution, print "NO".

Otherwise print "YES" and then *m* lines, the *i*-th of them is the weight of the *i*-th edge *w**i* (<=-<=2·*n*2<=≤<=*w**i*<=≤<=2·*n*2).

Demo Input:
['3 3\n2 2 2\n1 2\n2 3\n1 3\n', '4 3\n-1 0 2 1\n1 2\n2 3\n3 4\n', '6 6\n3 5 5 5 1 5\n1 4\n3 2\n4 3\n4 5\n3 5\n5 6\n', '4 4\n4 4 2 4\n1 2\n2 3\n3 4\n4 1\n']

Demo Output:
['YES\n1\n1\n1\n', 'YES\n-1\n1\n1\n', 'YES\n3\n5\n3\n-1\n-3\n5\n', 'NO']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a simple way to create hard tasks: take one simple problem as the query, and try to find an algorithm that can solve it faster than bruteforce. This kind of tasks usually appears in OI contest, and usually involves data structures.

Let's try to create a task, for example, we take the "Hamming distance problem": for two binary strings s and t with the same length, the Hamming distance between them is the number of positions at which the corresponding symbols are different. For example, the Hamming distance between "00111" and "10101" is 2 (the different symbols are marked with bold).

We use the Hamming distance problem as a query in the following way: you are given two strings a and b and several queries. Each query will be: what is the Hamming distance between two strings ap1ap1 + 1...ap1 + len - 1 and bp2bp2 + 1...bp2 + len - 1?

Note, that in this problem the strings are zero-based, that is s = s0s1... s|s| - 1.

Input

The first line contains a string a (1 ≤ |a| ≤ 200000). The second line contains a string b (1 ≤ |b| ≤ 200000). Each character of both strings is either "0" or "1".

The third line contains an integer q (1 ≤ q ≤ 400000) — the number of queries. Each of the following q lines contains three integers: p1, p2 and len (0 ≤ p1 ≤ |a| - len; 0 ≤ p2 ≤ |b| - len), these numbers denote the parameters of the current query.

Output

Output q integers — the answers for the queries.

Examples

Input

101010
11110000
3
0 0 3
2 3 4
5 7 1


Output

1
1
0


Input

10001010101011001010100101010011010
101010100101001010100100101010
5
0 0 12
3 9 7
6 4 15
12 15 10
13 3 20


Output

5
4
3
5
13

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Hoge is in trouble. He just bought a new mansion, but it’s haunted by a phantom. He asked a famous conjurer Dr. Huga to get rid of the phantom. Dr. Huga went to see the mansion, and found that the phantom is scared by its own mirror images. Dr. Huga set two flat mirrors in order to get rid of the phantom.

As you may know, you can make many mirror images even with only two mirrors. You are to count up the number of the images as his assistant. Given the coordinates of the mirrors and the phantom, show the number of images of the phantom which can be seen through the mirrors.



Input

The input consists of multiple test cases. Each test cases starts with a line which contains two positive integers, px and py (1 ≤ px, py ≤ 50), which are the x- and y-coordinate of the phantom. In the next two lines, each line contains four positive integers ux, uy, vx and vy (1 ≤ ux, uy, vx, vy ≤ 50), which are the coordinates of the mirror.

Each mirror can be seen as a line segment, and its thickness is negligible. No mirror touches or crosses with another mirror. Also, you can assume that no images will appear within the distance of 10-5 from the endpoints of the mirrors.

The input ends with a line which contains two zeros.

Output

For each case, your program should output one line to the standard output, which contains the number of images recognized by the phantom. If the number is equal to or greater than 100, print “TOO MANY” instead.

Example

Input

4 4
3 3 5 3
3 5 5 6
4 4
3 3 5 3
3 5 5 5
0 0


Output

4
TOO MANY

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write
```python
remove(text, what)
```
that takes in a string ```str```(```text``` in Python) and an object/hash/dict/Dictionary ```what``` and returns a string with the chars removed in ```what```.
For example:
```python
remove('this is a string',{'t':1, 'i':2}) == 'hs s a string'
# remove from 'this is a string' the first 1 't' and the first 2 i's.
remove('hello world',{'x':5, 'i':2}) == 'hello world'
# there are no x's or i's, so nothing gets removed
remove('apples and bananas',{'a':50, 'n':1}) == 'pples d bnns'
# we don't have 50 a's, so just remove it till we hit end of string.
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef is trying to decode some pattern problems, Chef wants your help to code it. Chef has one number K to form a new pattern. Help the chef to code this pattern problem.

-----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, one integer $K$. 

-----Output:-----
For each test case, output as the pattern.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq K \leq 100$

-----Sample Input:-----
4
1
2
3
4

-----Sample Output:-----
2
23
34
234
345
456
2345
3456
4567
5678

-----EXPLANATION:-----
No need, else pattern can be decode easily.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya's friends made him a birthday present — a bracket sequence. Petya was quite disappointed with his gift, because he dreamed of correct bracket sequence, yet he told his friends nothing about his dreams and decided to fix present himself. 

To make everything right, Petya is going to move at most one bracket from its original place in the sequence to any other position. Reversing the bracket (e.g. turning "(" into ")" or vice versa) isn't allowed. 

We remind that bracket sequence s is called correct if: 

  * s is empty; 
  * s is equal to "(t)", where t is correct bracket sequence; 
  * s is equal to t_1 t_2, i.e. concatenation of t_1 and t_2, where t_1 and t_2 are correct bracket sequences. 



For example, "(()())", "()" are correct, while ")(" and "())" are not. Help Petya to fix his birthday present and understand whether he can move one bracket so that the sequence becomes correct.

Input

First of line of input contains a single number n (1 ≤ n ≤ 200 000) — length of the sequence which Petya received for his birthday.

Second line of the input contains bracket sequence of length n, containing symbols "(" and ")".

Output

Print "Yes" if Petya can make his sequence correct moving at most one bracket. Otherwise print "No".

Examples

Input


2
)(


Output


Yes


Input


3
(()


Output


No


Input


2
()


Output


Yes


Input


10
)))))(((((


Output


No

Note

In the first example, Petya can move first bracket to the end, thus turning the sequence into "()", which is correct bracket sequence.

In the second example, there is no way to move at most one bracket so that the sequence becomes correct.

In the third example, the sequence is already correct and there's no need to move brackets.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A certain big IT company (which we will not name in order not to get sued) is preparing to launch a new version of its flagship product. Having just been employed as a developer on the project, you have been given a list of open bugs that should be fixed in the new version. 

Being bugs, you are not exactly certain how to fix them, even though you have some ideas. For each bug you are able to estimate your ability to quickly fix the bug. Of course, these estimates may be wrong, so if you try to fix a bug and fail, you will revise the estimate of your ability to fix this bug.

To be specific, we use the following probabilistic model for the bug fixing process: for each bug, there is an associated fix probability $p$. Every hour, you choose one bug to work on, and work on this bug for the entire hour (if you manage to fix the bug in less then an hour, you celebrate by having coffee and taunting your coworkers for the remaining part of the hour). The probability that you succeed in fixing the bug during this hour is $p$. If you fail to resolve the bug, the fix probability for this bug is reduced to $p \cdot f$, where $f \le 1$ is a factor indicating how much faith you lose in your ability after a failure. The fix probabilities for the other bugs remain unchanged. The next hour, you again choose an open bug to work on, and so on. This is repeated until the new version is released, and you are allowed to go home and sleep.

In addition, each bug has a severity $s$ indicating how severe the bug is (or alternatively, the value of fixing the bug). Clearly, it is possible that you will not manage to fix all the bugs before the product is released. In order to make as good an impression on your boss as possible, you would like to maximize the total severity of those bugs which you do manage to resolve, by carefully choosing which bugs to work on. What will be the expected value of the total severity of fixed bugs, provided that you, every hour, choose which bug to work on in such a way that this quantity is maximized?

-----Input-----
The first line of input contains three numbers $B$, $T$ and $f$, where $0 \le B \le 10$ is an integer giving the number of open bugs, $0 \le T \le 100$ is an integer giving the number of hours left until the new version is released, and $0 \le f \le 1$ is a real number as described above.

Each of the following $B$ lines describe an open bug. Each such description contains two numbers $p$ and $s$, where $0 \le p \le 1$ is a real number giving the initial fix probability of the bug and $0 \le s \le 10000$ is an integer giving the severity of the bug.

All real numbers are given with exactly $6$ digits after the decimal point.

-----Output-----
Output a line containing the expected total severity of bugs fixed, provided you work in a way which maximizes this quantity. Any answer with either absolute or relative error smaller than $10^{-6}$ is acceptable.

-----Examples-----
Sample Input:
1 2 0.950000
0.700000 50
Sample Output:
44.975

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