vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Some programming contest problems are really tricky: not only do they
require a different output format from what you might have expected, but
also the sample output does not show the difference. For an example,
let us look at permutations.

A permutation of the integers 1 to n is an
ordering of
these integers. So the natural way to represent a permutation is
to list the integers in this order. With n = 5, a
permutation might look like 2, 3, 4, 5, 1. 

However, there is another possibility of representing a permutation:
You create a list of numbers where the i-th number is the
position of the integer i in the permutation. 
Let us call this second
possibility an inverse permutation. The inverse permutation
for the sequence above is 5, 1, 2, 3, 4.

An ambiguous permutation is a permutation which cannot be
distinguished from its inverse permutation. The permutation 1, 4, 3, 2
for example is ambiguous, because its inverse permutation is the same.
To get rid of such annoying sample test cases, you have to write a
program which detects if a given permutation is ambiguous or not.

-----Input Specification-----
The input contains several test cases.

The first line of each test case contains an integer n
(1 ≤ n ≤ 100000).
Then a permutation of the integers 1 to n follows
in the next line. There is exactly one space character
between consecutive integers.
You can assume that every integer between 1 and n
appears exactly once in the permutation.

The last test case is followed by a zero.

-----Output Specification-----
For each test case output whether the permutation is ambiguous or not.
Adhere to the format shown in the sample output.

-----Sample Input-----
4
1 4 3 2
5
2 3 4 5 1
1
1
0

-----Sample Output-----
ambiguous
not ambiguous
ambiguous

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jon Snow is on the lookout for some orbs required to defeat the white walkers. There are k different types of orbs and he needs at least one of each. One orb spawns daily at the base of a Weirwood tree north of the wall. The probability of this orb being of any kind is equal. As the north of wall is full of dangers, he wants to know the minimum number of days he should wait before sending a ranger to collect the orbs such that the probability of him getting at least one of each kind of orb is at least $\frac{p_{i} - \epsilon}{2000}$, where ε < 10^{ - 7}.

To better prepare himself, he wants to know the answer for q different values of p_{i}. Since he is busy designing the battle strategy with Sam, he asks you for your help.


-----Input-----

First line consists of two space separated integers k, q (1 ≤ k, q ≤ 1000) — number of different kinds of orbs and number of queries respectively.

Each of the next q lines contain a single integer p_{i} (1 ≤ p_{i} ≤ 1000) — i-th query.


-----Output-----

Output q lines. On i-th of them output single integer — answer for i-th query.


-----Examples-----
Input
1 1
1

Output
1

Input
2 2
1
2

Output
2
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a doubly linked list of n nodes sorted by values, the task is to remove duplicate nodes present in the linked list.
Example 1:
Input:
n = 6
1<->1<->1<->2<->3<->4
Output:
1<->2<->3<->4
Explanation:
Only the first occurance of node with value 1 is 
retained, rest nodes with value = 1 are deleted.
Example 2:
Input:
n = 7
1<->2<->2<->3<->3<->4<->4
Output:
1<->2<->3<->4
Explanation:
Only the first occurance of nodes with values 2,3 and 4 are 
retained, rest repeating nodes are deleted.
Your Task:
You have to complete the method removeDuplicates() which takes 1 argument: the head of the linked list.  Your function should return a pointer to a linked list with no duplicate element.
Constraint:
1 <= n <= 10^{5}
Expected Time Complexity: O(n)
Expected Space Complexity: O(1)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Niwango bought a piece of land that can be represented as a half-open interval [0, X).

Niwango will lay out N vinyl sheets on this land. The sheets are numbered 1,2, \ldots, N, and they are distinguishable. For Sheet i, he can choose an integer j such that 0 \leq j \leq X - L_i and cover [j, j + L_i) with this sheet.

Find the number of ways to cover the land with the sheets such that no point in [0, X) remains uncovered, modulo (10^9+7). We consider two ways to cover the land different if and only if there is an integer i (1 \leq i \leq N) such that the region covered by Sheet i is different.

Constraints

* 1 \leq N \leq 100
* 1 \leq L_i \leq X \leq 500
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N X
L_1 L_2 \ldots L_N


Output

Print the answer.

Examples

Input

3 3
1 1 2


Output

10


Input

18 477
324 31 27 227 9 21 41 29 50 34 2 362 92 11 13 17 183 119


Output

134796357

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an unweighted, undirected graph. Write a program to check if it's a tree topology.

-----Input-----

The first line of the input file contains two integers N and M --- number of nodes and number of edges in the graph (0 < N <= 10000, 0 <= M <= 20000). Next M lines contain M edges of that graph --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u,v <= N).

-----Output-----

Print YES if the given graph is a tree, otherwise print NO.

-----Example-----
Input:
3 2
1 2
2 3

Output:
YES

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kefaa has developed a novel decomposition of a tree. He claims that this decomposition solves many difficult problems related to trees. However, he doesn't know how to find it quickly, so he asks you to help him.
You are given a tree with $N$ vertices numbered $1$ through $N$. Let's denote an edge between vertices $u$ and $v$ by $(u, v)$. The triple-tree decomposition is a partition of edges of the tree into unordered triples of edges $(a, b), (a, c), (a, d)$ such that $a \neq b \neq c \neq d$. Each edge must belong to exactly one triple.
Help Kefaa with this problem — find a triple-tree decomposition of the given tree or determine that no such decomposition exists.

-----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$.
- Each of the following $N-1$ lines contains two space-separated integers $u$ and $v$ describing an edge between vertices $u$ and $v$ of the tree.

-----Output-----
- For each test case, print a line containing the string "YES" if a triple-tree decomposition of the given tree exists or "NO" otherwise.
- If it exists, print $\frac{N-1}{3}$ more lines describing a decomposition.
- Each of these lines should contain four space-separated integers $a$, $b$, $c$ and $d$ describing a triple of edges $(a, b), (a, c), (a, d)$.
If more than one triple-tree decomposition exists, you may output any one.

-----Constraints-----
- $1 \le T \le 100$
- $2 \le N \le 2 \cdot 10^5$
- $1 \le u, v \le N$
- the sum of $N$ over all test cases does not exceed $2 \cdot 10^5$

-----Subtasks-----
Subtask #1 (20 points): $2 \le N \le 10$
Subtask #2 (30 points):$2 \le N \le 5000$ and the sum of $N$ overall testcases doesn't exceed $5000$
Subtask #3 (50 points): original constraints

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

-----Example Output-----
YES
1 2 3 4
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that takes a string and returns an array of the repeated characters (letters, numbers, whitespace) in the string.

If a charater is repeated more than once, only show it once in the result array.

Characters should be shown **by the order of their first repetition**. Note that this may be different from the order of first appearance of the character.

Characters are case sensitive.

For F# return a "char list"

## Examples:

```python
remember("apple") => returns ["p"]
remember("apPle") => returns []          # no repeats, "p" != "P"
remember("pippi") => returns ["p","i"]   # show "p" only once
remember('Pippi') => returns ["p","i"]   # "p" is repeated first
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence a_1, a_2, ..., a_{n} of one-dimensional segments numbered 1 through n. Your task is to find two distinct indices i and j such that segment a_{i} lies within segment a_{j}.

Segment [l_1, r_1] lies within segment [l_2, r_2] iff l_1 ≥ l_2 and r_1 ≤ r_2.

Print indices i and j. If there are multiple answers, print any of them. If no answer exists, print -1 -1.


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 3·10^5) — the number of segments.

Each of the next n lines contains two integers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ 10^9) — the i-th segment.


-----Output-----

Print two distinct indices i and j such that segment a_{i} lies within segment a_{j}. If there are multiple answers, print any of them. If no answer exists, print -1 -1.


-----Examples-----
Input
5
1 10
2 9
3 9
2 3
2 9

Output
2 1

Input
3
1 5
2 6
6 20

Output
-1 -1



-----Note-----

In the first example the following pairs are considered correct:  (2, 1), (3, 1), (4, 1), (5, 1) — not even touching borders;  (3, 2), (4, 2), (3, 5), (4, 5) — touch one border;  (5, 2), (2, 5) — match exactly.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
King Klee's kingdom is under attack. He leaves the task of protecting his kingdom to you as you are 
Now you are given N teams of soldiers. There are 3 gates --> Large, Larger, Largest.
You need to form three teams from these N teams to send them to those three gates.
But the order should follow certain conditions ...L1 ≥ L2 ≥ L3. where

L1, No. of soldiers at Largest gate.
L3, No. of soldiers at Larger gate.
L3, No. of soldiers at Large gate.
Remember you shouldn't waste all the soldiers at the Largest Gate i.e, L1 should be as small as possible.

Input
1st line --> N , integer value . 1 ≤ N ≤ 12
N lines --> integer values ≥ 1 and ≤ 100.
Output
The pair L1.

SAMPLE INPUT
4
3
3
1
4

SAMPLE OUTPUT
4

Explanation

The numbers are divided into three pairs P1, P2 and P3 following the condition P1 ≥ P2 ≥ P3 , if P1=4 i.e 3+1 ,  P2=4 and P3=3. Hence the answer is P1=4 .
Note : Here pair in the sense one/two/more than two numbers summed up.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string and an array of index numbers, return the characters of the string rearranged to be in the order specified by the accompanying array.

Ex:

scramble('abcd', [0,3,1,2]) -> 'acdb' 

The string that you will be returning back will have: 'a' at index 0, 'b' at index 3, 'c' at index 1, 'd' at index 2, because the order of those characters maps to their corisponding numbers in the index array. 


In other words, put the first character in the string at the index described by the first element of the array



You can assume that you will be given a string and array of equal length and both containing valid characters (A-Z, a-z, or 0-9).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dhruvil has always been a studious person and will be completing his Engineering soon. He is always kneen about solving problems and is preparing hard for his next interview at Hackerrank. He has practiced lots of problems and now he came across this problem.
Given a message containing English letters(A-Z), it is being encoded to numbers using the following mapping:
'A' -> 1,'B' -> 2 ……………… 'Z' -> 26.
Now, given a non-empty string containing only digits, help Dhruvil determine the total number of ways to decode it.
While decoding you need to choose a substring of charachters and not a subsequence. Also a chosen substring should not contain any leading "0"s, but can contain trailing "0"s. Since the output can be very large print the answer as modulo 10^9 + 7 i.e 1000000007.

-----Input:-----
The first line of the input consists of single integer T, the number of test cases.
Each test case consists of a string.

-----Output:-----
For each test case print a single integer - the total number of ways to decode the digit string.

-----Constraints-----
- $1 \leq T \leq 1000$
- $2 \leq S \leq 10^9$

-----Sample Input:-----
2
12

226

-----Sample Output:-----
2

3

-----EXPLANATION:-----
There are 2 possible ways. It could be decoded as "AB" {1,2} or "L" {12}.
There are 3 possible ways. It could be decoded as "BZ" {2,26}, "VF" {22,6}, or "BBF" {2,2,6}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of positive integers target and an array initial of same size with all zeros.
Return the minimum number of operations to form a target array from initial if you are allowed to do the following operation:

Choose any subarray from initial and increment each value by one.

The answer is guaranteed to fit within the range of a 32-bit signed integer.
 
Example 1:
Input: target = [1,2,3,2,1]
Output: 3
Explanation: We need at least 3 operations to form the target array from the initial array.
[0,0,0,0,0] increment 1 from index 0 to 4 (inclusive).
[1,1,1,1,1] increment 1 from index 1 to 3 (inclusive).
[1,2,2,2,1] increment 1 at index 2.
[1,2,3,2,1] target array is formed.

Example 2:
Input: target = [3,1,1,2]
Output: 4
Explanation: (initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target).

Example 3:
Input: target = [3,1,5,4,2]
Output: 7
Explanation: (initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] 
                                  -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target).

Example 4:
Input: target = [1,1,1,1]
Output: 1

 
Constraints:

1 <= target.length <= 10^5
1 <= target[i] <= 10^5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As we all know, Dart is some kind of creature from Upside Down world. For simplicity, we call their kind pollywogs. Dart and x - 1 other pollywogs are playing a game. There are n stones in a row, numbered from 1 through n from left to right. At most 1 pollywog may be sitting on each stone at a time. Initially, the pollywogs are sitting on the first x stones (one pollywog on each stone).

<image>

Dart and his friends want to end up on the last x stones. At each second, the leftmost pollywog should jump to the right. A pollywog can jump at most k stones; more specifically, a pollywog can jump from stone number i to stones i + 1, i + 2, ... i + k. A pollywog can't jump on an occupied stone. Jumping a distance i takes ci amounts of energy from the pollywog. 

Also, q stones are special Each time landing on a special stone p, takes wp amounts of energy (in addition to the energy for jump) from the pollywog. wp could be negative, in this case, it means the pollywog absorbs |wp| amounts of energy.

Pollywogs want to spend as little energy as possible (this value could be negative). 

They're just pollywogs, so they asked for your help. Tell them the total change in their energy, in case they move optimally.

Input

The first line of input contains four integers, x, k, n and q (1 ≤ x ≤ k ≤ 8, k ≤ n ≤ 108, 0 ≤ q ≤ min(25, n - x)) — the number of pollywogs, the maximum length of jump, the number of stones and the number of special stones.

The next line contains k integers, c1, c2, ... ck, separated by spaces (1 ≤ ci ≤ 109) — the energetic costs of jumps.

The next q lines contain description of the special stones. Each line contains two integers p and wp (x + 1 ≤ p ≤ n, |wp| ≤ 109). All p are distinct.

Output

Print the minimum amount of energy they need, in the first and only line of output.

Examples

Input

2 3 10 2
1 2 3
5 -10
6 1000


Output

6


Input

4 7 85 3
17 5 28 4 52 46 6
59 -76
33 -69
19 2018


Output

135

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya is a big fan of mathematics, especially its part related to fractions. Recently he learned that a fraction $\frac{a}{b}$ is called proper iff its numerator is smaller than its denominator (a < b) and that the fraction is called irreducible if its numerator and its denominator are coprime (they do not have positive common divisors except 1).

During his free time, Petya thinks about proper irreducible fractions and converts them to decimals using the calculator. One day he mistakenly pressed addition button ( + ) instead of division button (÷) and got sum of numerator and denominator that was equal to n instead of the expected decimal notation. 

Petya wanted to restore the original fraction, but soon he realized that it might not be done uniquely. That's why he decided to determine maximum possible proper irreducible fraction $\frac{a}{b}$ such that sum of its numerator and denominator equals n. Help Petya deal with this problem.

 


-----Input-----

In the only line of input there is an integer n (3 ≤ n ≤ 1000), the sum of numerator and denominator of the fraction.


-----Output-----

Output two space-separated positive integers a and b, numerator and denominator of the maximum possible proper irreducible fraction satisfying the given sum.


-----Examples-----
Input
3

Output
1 2

Input
4

Output
1 3

Input
12

Output
5 7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given $n$ integer numbers $a_1, a_2, \dots, a_n$. Consider graph on $n$ nodes, in which nodes $i$, $j$ ($i\neq j$) are connected if and only if, $a_i$ AND $a_j\neq 0$, where AND denotes the bitwise AND operation.

Find the length of the shortest cycle in this graph or determine that it doesn't have cycles at all.


-----Input-----

The first line contains one integer $n$ $(1 \le n \le 10^5)$ — number of numbers.

The second line contains $n$ integer numbers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{18}$).


-----Output-----

If the graph doesn't have any cycles, output $-1$. Else output the length of the shortest cycle.


-----Examples-----
Input
4
3 6 28 9

Output
4
Input
5
5 12 9 16 48

Output
3
Input
4
1 2 4 8

Output
-1


-----Note-----

In the first example, the shortest cycle is $(9, 3, 6, 28)$.

In the second example, the shortest cycle is $(5, 12, 9)$.

The graph has no cycles in the third example.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's define $S(x)$ to be the sum of digits of number $x$ written in decimal system. For example, $S(5) = 5$, $S(10) = 1$, $S(322) = 7$.

We will call an integer $x$ interesting if $S(x + 1) < S(x)$. In each test you will be given one integer $n$. Your task is to calculate the number of integers $x$ such that $1 \le x \le n$ and $x$ is interesting.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$)  — number of test cases.

Then $t$ lines follow, the $i$-th line contains one integer $n$ ($1 \le n \le 10^9$) for the $i$-th test case.


-----Output-----

Print $t$ integers, the $i$-th should be the answer for the $i$-th test case.


-----Examples-----

Input
5
1
9
10
34
880055535
Output
0
1
1
3
88005553


-----Note-----

The first interesting number is equal to $9$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string str containing only lowercase letters, generate a string with the same letters, but in uppercase.
Example 1:
Input:
str = "geeks"
Output: GEEKS
Example 2:
Input:
str = "geeksforgeeks"
Output: GEEKSFORGEEKS
Your Task:
You don't need to read input or print anything. Your task is to complete the function to_upper() which takes the string str as an argument and returns the resultant string.
Expected Time Complexity: O(length of the string).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ length of the string ≤ 50

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Winnie-the-Pooh likes honey very much! That is why he decided to visit his friends. Winnie has got three best friends: Rabbit, Owl and Eeyore, each of them lives in his own house. There are winding paths between each pair of houses. The length of a path between Rabbit's and Owl's houses is a meters, between Rabbit's and Eeyore's house is b meters, between Owl's and Eeyore's house is c meters.

For enjoying his life and singing merry songs Winnie-the-Pooh should have a meal n times a day. Now he is in the Rabbit's house and has a meal for the first time. Each time when in the friend's house where Winnie is now the supply of honey is about to end, Winnie leaves that house. If Winnie has not had a meal the required amount of times, he comes out from the house and goes to someone else of his two friends. For this he chooses one of two adjacent paths, arrives to the house on the other end and visits his friend. You may assume that when Winnie is eating in one of his friend's house, the supply of honey in other friend's houses recover (most probably, they go to the supply store).

Winnie-the-Pooh does not like physical activity. He wants to have a meal n times, traveling minimum possible distance. Help him to find this distance.


-----Input-----

First line contains an integer n (1 ≤ n ≤ 100) — number of visits.

Second line contains an integer a (1 ≤ a ≤ 100) — distance between Rabbit's and Owl's houses.

Third line contains an integer b (1 ≤ b ≤ 100) — distance between Rabbit's and Eeyore's houses.

Fourth line contains an integer c (1 ≤ c ≤ 100) — distance between Owl's and Eeyore's houses.


-----Output-----

Output one number — minimum distance in meters Winnie must go through to have a meal n times.


-----Examples-----
Input
3
2
3
1

Output
3

Input
1
2
3
5

Output
0



-----Note-----

In the first test case the optimal path for Winnie is the following: first have a meal in Rabbit's house, then in Owl's house, then in Eeyore's house. Thus he will pass the distance 2 + 1 = 3.

In the second test case Winnie has a meal in Rabbit's house and that is for him. So he doesn't have to walk anywhere at all.

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