vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Nick has n bottles of soda left after his birthday. Each bottle is described by two values: remaining amount of soda a_{i} and bottle volume b_{i} (a_{i} ≤ b_{i}).

Nick has decided to pour all remaining soda into minimal number of bottles, moreover he has to do it as soon as possible. Nick spends x seconds to pour x units of soda from one bottle to another.

Nick asks you to help him to determine k — the minimal number of bottles to store all remaining soda and t — the minimal time to pour soda into k bottles. A bottle can't store more soda than its volume. All remaining soda should be saved.


-----Input-----

The first line contains positive integer n (1 ≤ n ≤ 100) — the number of bottles.

The second line contains n positive integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 100), where a_{i} is the amount of soda remaining in the i-th bottle.

The third line contains n positive integers b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 100), where b_{i} is the volume of the i-th bottle.

It is guaranteed that a_{i} ≤ b_{i} for any i.


-----Output-----

The only line should contain two integers k and t, where k is the minimal number of bottles that can store all the soda and t is the minimal time to pour the soda into k bottles.


-----Examples-----
Input
4
3 3 4 3
4 7 6 5

Output
2 6

Input
2
1 1
100 100

Output
1 1

Input
5
10 30 5 6 24
10 41 7 8 24

Output
3 11



-----Note-----

In the first example Nick can pour soda from the first bottle to the second bottle. It will take 3 seconds. After it the second bottle will contain 3 + 3 = 6 units of soda. Then he can pour soda from the fourth bottle to the second bottle and to the third bottle: one unit to the second and two units to the third. It will take 1 + 2 = 3 seconds. So, all the soda will be in two bottles and he will spend 3 + 3 = 6 seconds to do it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Cat Cink is participating in a party in Prime Kingdom. There are n Cates there (include Cat Cink). The i-th Cat is ai years old.
They will have dinner around some round tables. You want to distribute Cates such that:
Each Cat is sitting at some table.
Each table has at least 3 Cats sitting around it.
The sum of ages of any two adjacent Cats around each table should be a prime number.
If k Cats c1, c2, ..., ck are sitting around table in clockwise order, then for 1 ≤ i ≤ k - 1: ci and ci + 1 are adjacent, and c1 and ck are also adjacent.
If it is possible to distribute the Cats in the desired manner, find out a way to do that.

Input

The first line contains single integer n (3 ≤ n ≤ 200): the number of Cats in this party.
The second line contains n integers ai (2 ≤ ai ≤ 104).

Output

If it is impossible to do this, output "Impossible".
Otherwise, in the first line output an integer m (): the number of tables.
Then output m lines, each line should start with an integer k -=– the number of Cats around that table, and then k numbers — indices of Cat sitting around that table in clockwise order.
If there are several possible arrangements, output any of them.

SAMPLE INPUT
4
3 4 8 9

SAMPLE OUTPUT
1
4 1 2 4 3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 Given an integer `n`, find the maximal number you can obtain by deleting exactly one digit of the given number.

# Example

 For `n = 152`, the output should be `52`;
 
 For `n = 1001`, the output should be `101`.
 
# Input/Output


 - `[input]` integer `n`

    Constraints: `10 ≤ n ≤ 1000000.`


 - `[output]` an integer

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two integers x and y are compatible, if the result of their bitwise "AND" equals zero, that is, a & b = 0. For example, numbers 90 (10110102) and 36 (1001002) are compatible, as 10110102 & 1001002 = 02, and numbers 3 (112) and 6 (1102) are not compatible, as 112 & 1102 = 102.

You are given an array of integers a1, a2, ..., an. Your task is to find the following for each array element: is this element compatible with some other element from the given array? If the answer to this question is positive, then you also should find any suitable element.

Input

The first line contains an integer n (1 ≤ n ≤ 106) — the number of elements in the given array. The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 4·106) — the elements of the given array. The numbers in the array can coincide.

Output

Print n integers ansi. If ai isn't compatible with any other element of the given array a1, a2, ..., an, then ansi should be equal to -1. Otherwise ansi is any such number, that ai & ansi = 0, and also ansi occurs in the array a1, a2, ..., an.

Examples

Input

2
90 36


Output

36 90

Input

4
3 6 3 6


Output

-1 -1 -1 -1

Input

5
10 6 9 8 2


Output

-1 8 2 2 8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
JATC loves Banh-mi (a Vietnamese food). His affection for Banh-mi is so much that he always has it for breakfast. This morning, as usual, he buys a Banh-mi and decides to enjoy it in a special way.

First, he splits the Banh-mi into n parts, places them on a row and numbers them from 1 through n. For each part i, he defines the deliciousness of the part as x_i ∈ \{0, 1\}. JATC's going to eat those parts one by one. At each step, he chooses arbitrary remaining part and eats it. Suppose that part is the i-th part then his enjoyment of the Banh-mi will increase by x_i and the deliciousness of all the remaining parts will also increase by x_i. The initial enjoyment of JATC is equal to 0.

For example, suppose the deliciousness of 3 parts are [0, 1, 0]. If JATC eats the second part then his enjoyment will become 1 and the deliciousness of remaining parts will become [1, \\_, 1]. Next, if he eats the first part then his enjoyment will become 2 and the remaining parts will become [\\_, \\_, 2]. After eating the last part, JATC's enjoyment will become 4.

However, JATC doesn't want to eat all the parts but to save some for later. He gives you q queries, each of them consisting of two integers l_i and r_i. For each query, you have to let him know what is the maximum enjoyment he can get if he eats all the parts with indices in the range [l_i, r_i] in some order.

All the queries are independent of each other. Since the answer to the query could be very large, print it modulo 10^9+7.

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 100 000).

The second line contains a string of n characters, each character is either '0' or '1'. The i-th character defines the deliciousness of the i-th part.

Each of the following q lines contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n) — the segment of the corresponding query.

Output

Print q lines, where i-th of them contains a single integer — the answer to the i-th query modulo 10^9 + 7.

Examples

Input

4 2
1011
1 4
3 4


Output

14
3


Input

3 2
111
1 2
3 3


Output

3
1

Note

In the first example: 

  * For query 1: One of the best ways for JATC to eats those parts is in this order: 1, 4, 3, 2. 
  * For query 2: Both 3, 4 and 4, 3 ordering give the same answer. 



In the second example, any order of eating parts leads to the same answer.

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

Complete the function that receives an array of strings (`arr`) as an argument and returns all the valid Roman numerals.

Basic Roman numerals are denoted as:

```
I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000
```

For the purposes of this kata we will consider valid only the numbers in range 0 - 5000 (both exclusive) since numbers >= 5000 were written in a different way (you had to place a heavy bar over the numeral that meant it was multiplied with 1000).

There are other ways of tackling this problem but the easiest is probably writing a Regular Expression.

### Let's break the problem down:

To match a set of characters `/[1-9]/`(single digits) you should take into consideration the Roman numbers `I, II, III, IV, V, VI, VII, VIII, IX`. This could be done by testing with `/IX|IV|V?I{0,3}/`. This part `/I{0,3}/` matches `I, II or III` but we have a `V` appearing 0 or 1 times because of the `?` so `/V?I{0,3}/` would match `I,II,III,V,VI,VII or VIII`. However there is one flaw with this. Do you see it? It is the fact that it would also match an empty string `""` because of the {0,3}. In order to pass the tests you will have to **filter out the empty strings** as well. So the entire part matches `I to IX`(inclusive) but what about larger digits?

Use the same logic for the digit in the tens place and the hundreds place. Be sure to wrap each part (units, tens, hundreds, thousands) in a pair of braces `(IX|IV|V?I{0,3})` and for the digit in the thousands place the logic is pretty straight forward, you just have to match `M` 0 to 4 times (since 5000 is not included). Wrap everything up with `^` and `$` to make sure you match the entire string (^ matches from the beginning of the string, while $ denotes the end, meaning there is nothing after that sign.

## Examples

```
["I", "IIV", "IVI", "IX", "XII", "MCD"] ==> ["I", "IX", "XII", "MCD"]

["MMMMCMXCIX", "MMDCXLIV", "MMCIX", "CLD", "LCD"]) ==> ["MMMMCMXCIX", "MMDCXLIV", "MMCIX"]
```

Good luck!

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Blake is the boss of Kris, however, this doesn't spoil their friendship. They often gather at the bar to talk about intriguing problems about maximising some values. This time the problem is really special.

You are given an array *a* of length *n*. The characteristic of this array is the value  — the sum of the products of the values *a**i* by *i*. One may perform the following operation exactly once: pick some element of the array and move to any position. In particular, it's allowed to move the element to the beginning or to the end of the array. Also, it's allowed to put it back to the initial position. The goal is to get the array with the maximum possible value of characteristic.

Input Specification:
The first line of the input contains a single integer *n* (2<=≤<=*n*<=≤<=200<=000) — the size of the array *a*.

The second line contains *n* integers *a**i* (1<=≤<=*i*<=≤<=*n*, |*a**i*|<=≤<=1<=000<=000) — the elements of the array *a*.

Output Specification:
Print a single integer — the maximum possible value of characteristic of *a* that can be obtained by performing no more than one move.

Demo Input:
['4\n4 3 2 5\n', '5\n1 1 2 7 1\n', '3\n1 1 2\n']

Demo Output:
['39', '49', '9']

Note:
In the first sample, one may pick the first element and place it before the third (before 5). Thus, the answer will be 3·1 + 2·2 + 4·3 + 5·4 = 39.

In the second sample, one may pick the fifth element of the array and place it before the third. The answer will be 1·1 + 1·2 + 1·3 + 2·4 + 7·5 = 49.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mister B once received a gift: it was a book about aliens, which he started read immediately. This book had c pages.

At first day Mister B read v_0 pages, but after that he started to speed up. Every day, starting from the second, he read a pages more than on the previous day (at first day he read v_0 pages, at second — v_0 + a pages, at third — v_0 + 2a pages, and so on). But Mister B is just a human, so he physically wasn't able to read more than v_1 pages per day.

Also, to refresh his memory, every day, starting from the second, Mister B had to reread last l pages he read on the previous day. Mister B finished the book when he read the last page for the first time.

Help Mister B to calculate how many days he needed to finish the book.


-----Input-----

First and only line contains five space-separated integers: c, v_0, v_1, a and l (1 ≤ c ≤ 1000, 0 ≤ l < v_0 ≤ v_1 ≤ 1000, 0 ≤ a ≤ 1000) — the length of the book in pages, the initial reading speed, the maximum reading speed, the acceleration in reading speed and the number of pages for rereading.


-----Output-----

Print one integer — the number of days Mister B needed to finish the book.


-----Examples-----
Input
5 5 10 5 4

Output
1

Input
12 4 12 4 1

Output
3

Input
15 1 100 0 0

Output
15



-----Note-----

In the first sample test the book contains 5 pages, so Mister B read it right at the first day.

In the second sample test at first day Mister B read pages number 1 - 4, at second day — 4 - 11, at third day — 11 - 12 and finished the book.

In third sample test every day Mister B read 1 page of the book, so he finished in 15 days.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
C: Canisal cryptography

problem

Ebi-chan was given the string C obtained by encrypting a non-negative integer D with "canisal cipher". This cipher replaces each number in decimal notation with a fixed number (not necessarily different from the original). Different numbers will not be replaced with the same number, and the same number will not be rewritten to a different number depending on the position of appearance.

For example, this encryption method can result in 2646 being 0545, but not 3456 being 1333 or 1333 being 3456.

Now, Ebi-chan has been told that the remainder of dividing D by 10 ^ 9 + 7 is M. At this time, output one that can be considered as D. If you can think of more than one, you can output any of them. However, it is assumed that there is no extra `0` at the beginning of D.

Input format


M
C


Constraint

* 0 \ leq M <10 ^ 9 + 7
* 1 \ leq | C | \ leq 10 ^ 5



Output format

Print a non-negative integer that can be considered as D on one line. If it does not exist, output `-1`.

Input example 1


2
1000000007


Output example 1


1000000009

The encryption method this time was to replace 0 with 0, 1 with 1, and 9 with 7.

Input example 2


3
1000000007


Output example 2


-1

Input example 3


1
01 01


Output example 3


-1

There is no extra `0` at the beginning of the D.

Input example 4


45
1000000023


Output example 4


6000000087

Since `1000000052` and` 2000000059` also satisfy the conditions, you can output them.

Input example 5


0
940578326285963740


Output example 5


123456789864197523





Example

Input

2
1000000007


Output

1000000009

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number N. The task is to return all the numbers less than or equal to N in increasing order, with the fact that absolute difference between any adjacent digits of number should be 1.
 
Example 1:
Input: N = 20
Output: 10 12
Explanation: Diff between 1 and 0 and
Diff between 1 and 2 is one.
Example 2:
Input:
N = 9
Output: -1
Explanation: No such number exist.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function absDifOne() which takes an integer as input and returns a list of numbers.
 
Expected Time Complexity : O(2^{Number of Digits in N})
Expected Auxiliary Space : O(2^{Number of Digits in N})
Constraints:
1 <= N <= 10^{12}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pizzahub has started Home Delivery scheme in one of his restaurants. As the scheme is new , the Manager appoints only one employee to deliver food to various locations. The delivery boy who has been appointed is an absent-minded chap. He always forgets to fill fuel in his delivery scooter. So what he does is that whenever the Manager sends him for delivery, he goes to the gas station from the restaurant first. He gets his tank filled and then he heads towards his destination. He will do this every single time irrespective of the destination. The delivery boy tries his best to be on time. And to do this, he will choose those paths(from restaurant to gas station AND gas station to destinaion) which cost him the least amount of time. Your task is to tell the Manager how much time can the delivery boy save if he had enough fuel in his scooter i.e. if he went to the destination directly without stopping for fuel (taking the path which costs him least amount of time).
The city has N streets numbered from 0 to N-1. The restaurant is on street number S, the gas station is on street number G and the food has to be delivered to street D . Note that S, G and D need not be distinct.
Input:

First line of the input contains a single integer N.
Then follows an NxN matrix T which is represented in N lines with N space separated integers on each line.
T[i][j] denotes the time taken to move from the ith street to jth street. Obviously, T[i][i] = 0. 
Next line contains a single integer M, the number of scenarios.
The following M lines contain 3 space separated integers S, G and D.
Output:

For each of the M scenarios, output the time taken by the delivery boy to deliver the food and the time he could have saved if he went directly from S to D.
Both these values must be on the same line separated by a single space.
Constraints:

1 ≤ N ≤ 100
1 ≤ M ≤ 10000
0 ≤ T[i][j] ≤ 100000
0 ≤ S,G,D ≤ N-1

SAMPLE INPUT
4
0 2 1 3
1 0 4 5
3 1 0 3
1 1 1 0
4
0 2 1
0 2 2
3 1 2
3 0 1

SAMPLE OUTPUT
2 0
1 0
3 2
3 2

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The polar bears are going fishing. They plan to sail from (*s**x*,<=*s**y*) to (*e**x*,<=*e**y*). However, the boat can only sail by wind. At each second, the wind blows in one of these directions: east, south, west or north. Assume the boat is currently at (*x*,<=*y*).
 -  If the wind blows to the east, the boat will move to (*x*<=+<=1,<=*y*). -  If the wind blows to the south, the boat will move to (*x*,<=*y*<=-<=1). -  If the wind blows to the west, the boat will move to (*x*<=-<=1,<=*y*). -  If the wind blows to the north, the boat will move to (*x*,<=*y*<=+<=1). 
Alternatively, they can hold the boat by the anchor. In this case, the boat stays at (*x*,<=*y*). Given the wind direction for *t* seconds, what is the earliest time they sail to (*e**x*,<=*e**y*)?

Input Specification:
The first line contains five integers *t*,<=*s**x*,<=*s**y*,<=*e**x*,<=*e**y* (1<=≤<=*t*<=≤<=105,<=<=-<=109<=≤<=*s**x*,<=*s**y*,<=*e**x*,<=*e**y*<=≤<=109). The starting location and the ending location will be different.

The second line contains *t* characters, the *i*-th character is the wind blowing direction at the *i*-th second. It will be one of the four possibilities: "E" (east), "S" (south), "W" (west) and "N" (north).

Output Specification:
If they can reach (*e**x*,<=*e**y*) within *t* seconds, print the earliest time they can achieve it. Otherwise, print "-1" (without quotes).

Demo Input:
['5 0 0 1 1\nSESNW\n', '10 5 3 3 6\nNENSWESNEE\n']

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

Note:
In the first sample, they can stay at seconds 1, 3, and move at seconds 2, 4.

In the second sample, they cannot sail to the destination.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Devu and his brother love each other a lot. As they are super geeks, they only like to play with arrays. They are given two arrays a and b by their father. The array a is given to Devu and b to his brother. 

As Devu is really a naughty kid, he wants the minimum value of his array a should be at least as much as the maximum value of his brother's array b. 

Now you have to help Devu in achieving this condition. You can perform multiple operations on the arrays. In a single operation, you are allowed to decrease or increase any element of any of the arrays by 1. Note that you are allowed to apply the operation on any index of the array multiple times.

You need to find minimum number of operations required to satisfy Devu's condition so that the brothers can play peacefully without fighting. 


-----Input-----

The first line contains two space-separated integers n, m (1 ≤ n, m ≤ 10^5). The second line will contain n space-separated integers representing content of the array a (1 ≤ a_{i} ≤ 10^9). The third line will contain m space-separated integers representing content of the array b (1 ≤ b_{i} ≤ 10^9).


-----Output-----

You need to output a single integer representing the minimum number of operations needed to satisfy Devu's condition.


-----Examples-----
Input
2 2
2 3
3 5

Output
3

Input
3 2
1 2 3
3 4

Output
4

Input
3 2
4 5 6
1 2

Output
0



-----Note-----

In example 1, you can increase a_1 by 1 and decrease b_2 by 1 and then again decrease b_2 by 1. Now array a will be [3; 3] and array b will also be [3; 3]. Here minimum element of a is at least as large as maximum element of b. So minimum number of operations needed to satisfy Devu's condition are 3.

In example 3, you don't need to do any operation, Devu's condition is already satisfied.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number N, the task is to find the number of diagonals in N sided convex polygon.
Example 1:
Input: N = 5
Output: 5
Example 2:
Input: N = 6
Output: 9
Your Task:  
You don't need to read input or print anything. Your task is to complete the function diagonals() which takes N as input and returns the number of possible diagonals.
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
Constraints:
3 ≤ N ≤ 10^{9}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation).
Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.
 
Example 1:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)
Example 2:
Input: a = 4, b = 2, c = 7
Output: 1

Example 3:
Input: a = 1, b = 2, c = 3
Output: 0

 
Constraints:

1 <= a <= 10^9
1 <= b <= 10^9
1 <= c <= 10^9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya's got a birthday coming up and his mom decided to give him an array of positive integers a of length n.

Vasya thinks that an array's beauty is the greatest common divisor of all its elements. His mom, of course, wants to give him as beautiful an array as possible (with largest possible beauty). Unfortunately, the shop has only one array a left. On the plus side, the seller said that he could decrease some numbers in the array (no more than by k for each number).

The seller can obtain array b from array a if the following conditions hold: b_{i} > 0; 0 ≤ a_{i} - b_{i} ≤ k for all 1 ≤ i ≤ n.

Help mom find the maximum possible beauty of the array she will give to Vasya (that seller can obtain).


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 3·10^5; 1 ≤ k ≤ 10^6). The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^6) — array a.


-----Output-----

In the single line print a single number — the maximum possible beauty of the resulting array.


-----Examples-----
Input
6 1
3 6 10 12 13 16

Output
3

Input
5 3
8 21 52 15 77

Output
7



-----Note-----

In the first sample we can obtain the array:

3 6 9 12 12 15

In the second sample we can obtain the next array:

7 21 49 14 77

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