vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A pitch-black room

When I woke up, Mr. A was in a pitch-black room. Apparently, Mr. A got lost in a dungeon consisting of N rooms. You couldn't know which room A got lost in, but fortunately he got a map of the dungeon. Let's show A the way to go and lead to a bright room.

It is known that M of the N rooms are pitch black, and the D_1, D_2, ..., and D_Mth rooms are pitch black, respectively. Also, there are exactly K one-way streets from all the rooms in order, and the roads from the i-th room are v_ {i, 1}, v_ {i, 2}, ..., v_ {i, respectively. , K} Connected to the third room. You can follow the a_1, a_2, ..., a_lth roads in order from the room you are in for Mr. A. However, when Mr. A reaches the bright room, he ignores the subsequent instructions. You cannot know the information of the room where Mr. A is currently before and after the instruction, so you must give the instruction sequence so that you can reach the bright room no matter which room you are in. Answer the length of the shortest of such instructions.

Constraints

* 2 ≤ N ≤ 100
* 1 ≤ M ≤ min (16, N − 1)
* 1 ≤ K ≤ N
* 1 ≤ D_i ≤ N
* D_i are all different
* 1 ≤ v_ {i, j} ≤ N
* All dark rooms can reach at least one bright room



Input Format

Input is given from standard input in the following format.


NMK
D_1 D_2 ... D_M
v_ {1,1} v_ {1,2} ... v_ {1,K}
v_ {2,1} v_ {2,2} ... v_ {2, K}
...
v_ {N, 1} v_ {N, 2} ... v_ {N, K}


Output Format

Print the answer in one line.

Sample Input 1


4 2 2
1 2
twenty four
3 1
4 2
13


Sample Output 1


2


<image>
If you give the instruction 1, 1

* If A's initial position is room 1, the second move will reach room 3.
* If A's initial position is room 2, the first move will reach room 3.



Sample Input 2


3 2 2
1 2
twenty three
1 2
twenty one


Sample Output 2


3


<image>
If you give instructions 2, 1, 2

* If A's initial position is room 1, the first move will reach room 3.
* If A's initial position is room 2, the third move will reach room 3.



Sample Input 3


6 3 3
one two Three
4 1 1
2 5 2
3 3 6
4 4 4
5 5 5
6 6 6


Sample Output 3


3


<image>
Beware of unconnected cases and cases with self-edges and multiple edges.





Example

Input

4 2 2
1 2
2 4
3 1
4 2
1 3


Output

2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given K prime numbers and T queries of form Ai, Bi, for each query print the number of integers between Ai and Bi (both inclusive) that are divisible by atleast one of the K given primes.     

Input
First line: K and T. 
Second line: K primes.
Next T lines, each contain Ai, Bi.    

Output
Print T lines, denoting the answer to each of the T queries.

Constraints
1 ≤ K ≤ 10 
1 ≤ T ≤ 100 
1 ≤ A ≤ B ≤ 10^9 
Each prime ≤ 10^7

SAMPLE INPUT
2 1
2 3
1 10

SAMPLE OUTPUT
7

Explanation

2,3,4,6,8,9,10 are the 7 numbers.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarpus plays with red and blue marbles. He put *n* marbles from the left to the right in a row. As it turned out, the marbles form a zebroid.

A non-empty sequence of red and blue marbles is a zebroid, if the colors of the marbles in this sequence alternate. For example, sequences (red; blue; red) and (blue) are zebroids and sequence (red; red) is not a zebroid.

Now Polycarpus wonders, how many ways there are to pick a zebroid subsequence from this sequence. Help him solve the problem, find the number of ways modulo 1000000007 (109<=+<=7).

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=106) — the number of marbles in Polycarpus's sequence.

Output Specification:
Print a single number — the answer to the problem modulo 1000000007 (109<=+<=7).

Demo Input:
['3\n', '4\n']

Demo Output:
['6\n', '11\n']

Note:
Let's consider the first test sample. Let's assume that Polycarpus initially had sequence (red; blue; red), so there are six ways to pick a zebroid: 
 -  pick the first marble; -  pick the second marble; -  pick the third marble; -  pick the first and second marbles; -  pick the second and third marbles; -  pick the first, second and third marbles. 
It can be proven that if Polycarpus picks (blue; red; blue) as the initial sequence, the number of ways won't change.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given strings S and T consisting of lowercase English letters.
You can perform the following operation on S any number of times:
Operation: Choose two distinct lowercase English letters c_1 and c_2, then replace every occurrence of c_1 with c_2, and every occurrence of c_2 with c_1.
Determine if S and T can be made equal by performing the operation zero or more times.

-----Constraints-----
 - 1 \leq |S| \leq 2 \times 10^5
 - |S| = |T|
 - S and T consists of lowercase English letters.

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

-----Output-----
If S and T can be made equal, print Yes; otherwise, print No.

-----Sample Input-----
azzel
apple

-----Sample Output-----
Yes

azzel can be changed to apple, as follows:
 - Choose e as c_1 and l as c_2. azzel becomes azzle.
 - Choose z as c_1 and p as c_2. azzle becomes apple.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Karan and Akshay love challenging each other with awesome algorithmic questions. Today, Karan decided to give Akshay a relatively easy question. Karan has string s of length N consisting entirely of lowercase latin characters and he loves double palindromes (defined below). So he asks Akshay Q questions about the string of the type -

l r - consider the substring s[l...r] and report if the characters in this substring can be rearranged to form a double palindrome.

A palindrome is a string that read same forwards and backwards.

Let's define a double palindrome as a string that is concatenation of two palindrome, "AB" is a double palindrome if "A" and "B" are palindrome.

Eg. "abbacddc" is a double palindrome because "abba" and "cddc" are both palindromes.

But, Akshay is a very lazy guy. He asks you to solve the task at hand!(Height of laziness!)

If it is possible then print "YES", without quotes else print "NO".

Input format
The first line of input contains one integer N denoting the size of the string.

The second line of input contains the string s itself. It is guaranteed that the string consists only of lowercase latin characters.

The third line contains one integer Q denoting the total number of queries.

Next Q lines each contain two integers l r denoting the queries.

Output format
For each query output a single line with the string "YES" if the characters in the substring represented by the corresponding query can be rearranged to form double palindrome else output the string "NO".

Constraints

 1 ≤ N ≤ 10^5 
 1 ≤ Q ≤ 10^5 
 1 ≤ l ≤ r ≤ N 

Sub-tasks
For 25% points :  1 ≤ N, Q ≤ 10^3 

For 75% points : original constraints

Note : Output is case sensitive

Note : Palindrome can't be empty

SAMPLE INPUT
8
abcdabcd
2
1 8
3 5

SAMPLE OUTPUT
YES
NO

Explanation

For query 1, the substring can be rearranged to make the string "abbacddc" which is a double palindrome because "abba" and "cddc" are both palindromes.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A space explorer's ship crashed on Mars! They send a series of SOS messages to Earth for help. 

Letters in some of the SOS messages are altered by cosmic radiation during transmission. Given the signal received by Earth as a string, $\boldsymbol{\mathrm{~S~}}$, determine how many letters of the SOS message have been changed by radiation.

Example  

$s=\text{'SOSTOT'}$  

The original message was SOSSOS.  Two of the message's characters were changed in transit.  

Function Description

Complete the marsExploration function in the editor below.  

marsExploration has the following parameter(s):

string s: the string as received on Earth  

Returns  

int: the number of letters changed during transmission  

Input Format

There is one line of input: a single string, $\boldsymbol{\mathrm{~S~}}$. 

Constraints

$1\leq\ \text{length of}\ s\leq99$
$\textbf{length of}~s~\textbf{modulo}~~3=0$
$\boldsymbol{\mathrm{~S~}}$ will contain only uppercase English letters, ascii[A-Z].

Sample Input 0
SOSSPSSQSSOR

Sample Output 0
3

Explanation 0

$\boldsymbol{\mathrm{~S~}}$ = SOSSPSSQSSOR, and signal length $\textbf{|s|}=\textbf{12}$. They sent $4$ SOS messages (i.e.: $12/3=4$).

Expected signal: SOSSOSSOSSOS
Recieved signal: SOSSPSSQSSOR
Difference:          X  X   X

Sample Input 1
SOSSOT

Sample Output 1
1

Explanation 1

$\boldsymbol{\mathrm{~S~}}$ = SOSSOT, and signal length $|s|=6$. They sent $2$ SOS messages (i.e.: $6/3=2$).

Expected Signal: SOSSOS     
Received Signal: SOSSOT
Difference:           X

Sample Input 2
SOSSOSSOS

Sample Output 2
0

Explanation 2

Since no character is altered, return 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
User ainta decided to paint a wall. The wall consists of n2 tiles, that are arranged in an n × n table. Some tiles are painted, and the others are not. As he wants to paint it beautifully, he will follow the rules below.

  1. Firstly user ainta looks at the wall. If there is at least one painted cell on each row and at least one painted cell on each column, he stops coloring. Otherwise, he goes to step 2. 
  2. User ainta choose any tile on the wall with uniform probability. 
  3. If the tile he has chosen is not painted, he paints the tile. Otherwise, he ignores it. 
  4. Then he takes a rest for one minute even if he doesn't paint the tile. And then ainta goes to step 1. 



However ainta is worried if it would take too much time to finish this work. So he wants to calculate the expected time needed to paint the wall by the method above. Help him find the expected time. You can assume that choosing and painting any tile consumes no time at all. 

Input

The first line contains two integers n and m (1 ≤ n ≤ 2·103; 0 ≤ m ≤ min(n2, 2·104)) — the size of the wall and the number of painted cells.

Next m lines goes, each contains two integers ri and ci (1 ≤ ri, ci ≤ n) — the position of the painted cell. It is guaranteed that the positions are all distinct. Consider the rows of the table are numbered from 1 to n. Consider the columns of the table are numbered from 1 to n.

Output

In a single line print the expected time to paint the wall in minutes. Your answer will be considered correct if it has at most 10 - 4 absolute or relative error.

Examples

Input

5 2
2 3
4 1


Output

11.7669491886


Input

2 2
1 1
1 2


Output

2.0000000000


Input

1 1
1 1


Output

0.0000000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The mayor of the Central Town wants to modernize Central Street, represented in this problem by the $(Ox)$ axis.

On this street, there are $n$ antennas, numbered from $1$ to $n$. The $i$-th antenna lies on the position $x_i$ and has an initial scope of $s_i$: it covers all integer positions inside the interval $[x_i - s_i; x_i + s_i]$.

It is possible to increment the scope of any antenna by $1$, this operation costs $1$ coin. We can do this operation as much as we want (multiple times on the same antenna if we want).

To modernize the street, we need to make all integer positions from $1$ to $m$ inclusive covered by at least one antenna. Note that it is authorized to cover positions outside $[1; m]$, even if it's not required.

What is the minimum amount of coins needed to achieve this modernization?


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 80$ and $n \le m \le 100\ 000$).

The $i$-th of the next $n$ lines contains two integers $x_i$ and $s_i$ ($1 \le x_i \le m$ and $0 \le s_i \le m$).

On each position, there is at most one antenna (values $x_i$ are pairwise distinct).


-----Output-----

You have to output a single integer: the minimum amount of coins required to make all integer positions from $1$ to $m$ inclusive covered by at least one antenna.


-----Examples-----
Input
3 595
43 2
300 4
554 10

Output
281

Input
1 1
1 1

Output
0

Input
2 50
20 0
3 1

Output
30

Input
5 240
13 0
50 25
60 5
155 70
165 70

Output
26



-----Note-----

In the first example, here is a possible strategy:

  Increase the scope of the first antenna by $40$, so that it becomes $2 + 40 = 42$. This antenna will cover interval $[43 - 42; 43 + 42]$ which is $[1; 85]$  Increase the scope of the second antenna by $210$, so that it becomes $4 + 210 = 214$. This antenna will cover interval $[300 - 214; 300 + 214]$, which is $[86; 514]$  Increase the scope of the third antenna by $31$, so that it becomes $10 + 31 = 41$. This antenna will cover interval $[554 - 41; 554 + 41]$, which is $[513; 595]$ 

Total cost is $40 + 210 + 31 = 281$. We can prove that it's the minimum cost required to make all positions from $1$ to $595$ covered by at least one antenna.

Note that positions $513$ and $514$ are in this solution covered by two different antennas, but it's not important.

—

In the second example, the first antenna already covers an interval $[0; 2]$ so we have nothing to do.

Note that the only position that we needed to cover was position $1$; positions $0$ and $2$ are covered, but it's not important.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a matrix with n rows and m columns. Your task is to find the kth element which is obtained while traversing the matrix spirally. You need to complete the method findK which takes four arguments the first argument is the matrix A and the next two arguments will be n and m denoting the size of the matrix A and then the forth argument is an integer k. The function will return the kth element obtained while traversing the matrix spirally.
Example 1:
Input:
n = 4, m = 4, k = 10
A[][] = {{1  2  3  4},
         {5  6  7  8},
         {9  10 11 12},
         {13 14 15 16}}
Output:
14
Explanation:
The spiral order of matrix will look like 1->2->3->4->8->12->16->15->14->13->9->5->6->7->11->10. So the 10th element in this order is 14. 
Example 2:
Input:
n = 3, m = 3, k = 4
A[][] = {{1 2 3},
         {4 5 6},
         {7 8 9}}
Output:
6
Explanation:
The spiral order of matrix will look like 1->2->3->6->9->8->7->4->5. So the 4th element in this order is 6.
Your Task:
You only need to implement the given function findK(). Do not read input, instead use the arguments given in the function. Return the K'th element obtained by traversing matrix spirally.
Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n*m)
Constraints:
1<=n,m<=10^{3}
1<=k<=n*m

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Basin City is known for her incredibly high crime rates. The police see no option but to tighten security. They want to install traffic drones at different intersections to observe who’s running on a red light. If a car runs a red light, the drone will chase and stop the car to give the driver an appropriate ticket. The drones are quite stupid, however, and a drone will stop before it comes to the next intersection as it might otherwise lose its way home, its home being the traffic light to which it is assigned. The drones are not able to detect the presence of other drones, so the police’s R&D department found out that if a drone was placed at some intersection, then it was best not to put any drones at any of the neighbouring intersections. As is usual in many cities, there are no intersections in Basin City with more than four other neighbouring intersections.

The drones are government funded, so the police force would like to buy as many drones as they are allowed to. Being the programmer-go-to for the Basin City Police Department, they ask you to decide, for a given number of drones, whether it is feasible to position exactly this number of drones.

-----Input-----
The first line contains an integer $k$ ($0 \leq k \leq 15$), giving the number of drones to position. Then follows one line with $1 \leq n \leq 100\; 000$, the total number of intersections in Basin City. Finally follow $n$ lines describing consecutive intersections. The $i$-th line describes the $i$-th intersection in the following format: The line starts with one integer $d$ ($0 \leq d \leq 4$) describing the number of intersections neighbouring the $i$-th one. Then follow $d$ integers denoting the indices of these neighbouring intersections. They will be all distinct and different from $i$. The intersections are numbered from $1$ to $n$.

-----Output-----
If it is possible to position $k$ drones such that no two neighbouring intersections have been assigned a drone, output a single line containing possible. Otherwise, output a single line containing impossible.

-----Examples-----
Sample Input:
4
7
2 2 4
3 1 3 5
1 2
2 1 5
4 2 6 4 7
2 5 7
2 6 5
Sample Output:
impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a programming language in which every program is a non-empty sequence of "<" and ">" signs and digits. Let's explain how the interpreter of this programming language works. A program is interpreted using movement of instruction pointer (IP) which consists of two parts.

  * Current character pointer (CP); 
  * Direction pointer (DP) which can point left or right; 



Initially CP points to the leftmost character of the sequence and DP points to the right.

We repeat the following steps until the first moment that CP points to somewhere outside the sequence.

  * If CP is pointing to a digit the interpreter prints that digit then CP moves one step according to the direction of DP. After that the value of the printed digit in the sequence decreases by one. If the printed digit was 0 then it cannot be decreased therefore it's erased from the sequence and the length of the sequence decreases by one. 
  * If CP is pointing to "<" or ">" then the direction of DP changes to "left" or "right" correspondingly. Then CP moves one step according to DP. If the new character that CP is pointing to is "<" or ">" then the previous character will be erased from the sequence. 



If at any moment the CP goes outside of the sequence the execution is terminated.

It's obvious the every program in this language terminates after some steps.

We have a sequence s1, s2, ..., sn of "<", ">" and digits. You should answer q queries. Each query gives you l and r and asks how many of each digit will be printed if we run the sequence sl, sl + 1, ..., sr as an independent program in this language.

Input

The first line of input contains two integers n and q (1 ≤ n, q ≤ 100) — represents the length of the sequence s and the number of queries. 

The second line contains s, a sequence of "<", ">" and digits (0..9) written from left to right. Note, that the characters of s are not separated with spaces. 

The next q lines each contains two integers li and ri (1 ≤ li ≤ ri ≤ n) — the i-th query.

Output

For each query print 10 space separated integers: x0, x1, ..., x9 where xi equals the number of times the interpreter prints i while running the corresponding program. Print answers to the queries in the order they are given in input.

Examples

Input

7 4
1&gt;3&gt;22&lt;
1 3
4 7
7 7
1 7


Output

0 1 0 1 0 0 0 0 0 0 
2 2 2 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
2 3 2 1 0 0 0 0 0 0 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a sequence A composed of N positive integers: A_{1}, A_{2}, \cdots, A_{N}.
You will now successively do the following Q operations:
 - In the i-th operation, you replace every element whose value is B_{i} with C_{i}.
For each i (1 \leq i \leq Q), find S_{i}: the sum of all elements in A just after the i-th operation.

-----Constraints-----
 - All values in input are integers.
 -  1 \leq N, Q, A_{i}, B_{i}, C_{i} \leq 10^{5} 
 -  B_{i} \neq C_{i} 

-----Input-----
Input is given from Standard Input in the following format:
N
A_{1} A_{2} \cdots A_{N}
Q
B_{1} C_{1}
B_{2} C_{2}
\vdots
B_{Q} C_{Q}

-----Output-----
Print Q integers S_{i} to Standard Output in the following format:
S_{1}
S_{2}
\vdots
S_{Q}

Note that S_{i} may not fit into a 32-bit integer.

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

-----Sample Output-----
11
12
16

Initially, the sequence A is 1,2,3,4.
After each operation, it becomes the following:
 - 2, 2, 3, 4
 - 2, 2, 4, 4
 - 4, 4, 4, 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko got a set of intervals for his birthday. There are many games he can play with them. In one of them, Mirko must find the longest sequence of distinct intervals such that each interval in the sequence is in the set and that each interval contains the one that follows in the sequence.

Write a program which finds one such longest sequence.

-----Input-----
The first line of input contains the integer $N$ $(1 \le N \le 100000)$, the number of intervals in the set.

Each of the following $N$ lines contains two integers $A$ and $B$ describing one interval $(1 \le A < B \le 1000000)$.

-----Output-----
Output the length $K$ of the longest sequence on the first line.

Each of the following $K$ lines should contain one element of the sequence, an interval in the same format it was given in the input.

-----Examples-----
Sample Input 1:
3
3 4
2 5
1 6
Sample Output 1:
3
1 6
2 5
3 4

Sample Input 2:
5
10 30
20 40
30 50
10 60
30 40
Sample Output 2:
3
10 60
30 50
30 40

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Last winter, an avalanche swept away all the ski lifts from the ski resort Valen. Instead of rebuilding the lifts like they were before, the plan is to do it in a more optimized way, and you are responsible for this. 

The only thing remaining from the old lift system are $n$ pylons situated at integer coordinates in the plane. You would like to put lifts in the form of line segments between some of these pylons. The line segments must satisfy the following constraints:
 - A line segment can only go between pylons $(x_1, y_1)$ and $(x_2, y_2)$ if $|y_1-y_2| = 1$.
 - There are two types of pylons, one-way and two-way pylons. The one-way pylons can be connected to at most one other pylon, and the two-way pylons can be connected to at most two other pylons. However, if a two-way pylon $i$ is connected to two other pylons, then they must be on opposite sides of $i$ in the $y$-direction. In other words, the two pylons connected to $i$ must have different $y$-coordinates.
 - Two line segments may not intersect (except that the two line segments incident on a two-way pylon may touch at their endpoints).

What is the maximum number of ski lifts (line segments) you can place under these constraints?

-----Input-----
The first line contains one integer $n$ ($1 \leq n \leq 10^5$). Each of the following $n$ lines contains three integers $x$, $y$, and $a$, the coordinates and type of a pylon ($0 \leq x,y \leq 10^5$; $a=1$ for a one-way pylon and $a=2$ for a two-way pylon). All the pylons are situated at different coordinates.

-----Output-----
Output the maximum number of ski lift line segments that can be placed.

-----Examples-----
Sample Input:
8
1 0 1
3 0 2
0 1 1
2 1 2
4 1 2
1 2 2
2 3 1
4 3 1
Sample Output:
4

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