vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
As you could know there are no male planes nor female planes. However, each plane on Earth likes some other plane. There are n planes on Earth, numbered from 1 to n, and the plane with number i likes the plane with number fi, where 1 ≤ fi ≤ n and fi ≠ i.

We call a love triangle a situation in which plane A likes plane B, plane B likes plane C and plane C likes plane A. Find out if there is any love triangle on Earth.

Input

The first line contains a single integer n (2 ≤ n ≤ 5000) — the number of planes.

The second line contains n integers f1, f2, ..., fn (1 ≤ fi ≤ n, fi ≠ i), meaning that the i-th plane likes the fi-th.

Output

Output «YES» if there is a love triangle consisting of planes on Earth. Otherwise, output «NO».

You can output any letter in lower case or in upper case.

Examples

Input

5
2 4 5 1 3


Output

YES


Input

5
5 5 5 5 1


Output

NO

Note

In first example plane 2 likes plane 4, plane 4 likes plane 1, plane 1 likes plane 2 and that is a love triangle.

In second example there are no love triangles.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fedya studies in a gymnasium. Fedya's maths hometask is to calculate the following expression:(1^{n} + 2^{n} + 3^{n} + 4^{n}) mod 5

for given value of n. Fedya managed to complete the task. Can you? Note that given number n can be extremely large (e.g. it can exceed any integer type of your programming language).


-----Input-----

The single line contains a single integer n (0 ≤ n ≤ 10^10^5). The number doesn't contain any leading zeroes.


-----Output-----

Print the value of the expression without leading zeros.


-----Examples-----
Input
4

Output
4

Input
124356983594583453458888889

Output
0



-----Note-----

Operation x mod y means taking remainder after division x by y.

Note to the first sample:

[Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of size n, Find the subarray with least average of size k.
 
Example 1:
Input: nums = [30, 20, 10], k = 1
Output: 3
Explanation: Subarrays of length 1 are
{30}, {20}, {10}. {10} has the least 
average.
Example 2:
Input: nums = [30, 20, 10], k = 2
Output: 2
Explanation: Subarrays of length 2 are
{30, 20}, {20, 10}. {20, 10} has the least 
average.
 
Your Task:
You don't need to read or print anything. Yous task is to complete the function least_average() which takes the array and k as input parameter and returns the index of the first element of the subarray(1-based indexing) of size k that has least average.
 
Expected Time Complexity: O(n)
Expected Space Compelxity: O(1)
 
Constraints:
1 <= k <= n <= 100000
1 <= elements of array <= 1000000

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The country of Byalechinsk is running elections involving *n* candidates. The country consists of *m* cities. We know how many people in each city voted for each candidate.

The electoral system in the country is pretty unusual. At the first stage of elections the votes are counted for each city: it is assumed that in each city won the candidate who got the highest number of votes in this city, and if several candidates got the maximum number of votes, then the winner is the one with a smaller index.

At the second stage of elections the winner is determined by the same principle over the cities: the winner of the elections is the candidate who won in the maximum number of cities, and among those who got the maximum number of cities the winner is the one with a smaller index.

Determine who will win the elections.

Input Specification:
The first line of the input contains two integers *n*, *m* (1<=≤<=*n*,<=*m*<=≤<=100) — the number of candidates and of cities, respectively.

Each of the next *m* lines contains *n* non-negative integers, the *j*-th number in the *i*-th line *a**ij* (1<=≤<=*j*<=≤<=*n*, 1<=≤<=*i*<=≤<=*m*, 0<=≤<=*a**ij*<=≤<=109) denotes the number of votes for candidate *j* in city *i*.

It is guaranteed that the total number of people in all the cities does not exceed 109.

Output Specification:
Print a single number — the index of the candidate who won the elections. The candidates are indexed starting from one.

Demo Input:
['3 3\n1 2 3\n2 3 1\n1 2 1\n', '3 4\n10 10 3\n5 1 6\n2 2 2\n1 5 7\n']

Demo Output:
['2', '1']

Note:
Note to the first sample test. At the first stage city 1 chosen candidate 3, city 2 chosen candidate 2, city 3 chosen candidate 2. The winner is candidate 2, he gained 2 votes.

Note to the second sample test. At the first stage in city 1 candidates 1 and 2 got the same maximum number of votes, but candidate 1 has a smaller index, so the city chose candidate 1. City 2 chosen candidate 3. City 3 chosen candidate 1, due to the fact that everyone has the same number of votes, and 1 has the smallest index. City 4 chosen the candidate 3. On the second stage the same number of cities chose candidates 1 and 3. The winner is candidate 1, the one with the smaller index.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Andrew and Eugene are playing a game. Initially, Andrew has string s, consisting of digits. Eugene sends Andrew multiple queries of type "di → ti", that means "replace all digits di in string s with substrings equal to ti". For example, if s = 123123, then query "2 → 00" transforms s to 10031003, and query "3 → " ("replace 3 by an empty string") transforms it to s = 1212. After all the queries Eugene asks Andrew to find the remainder after division of number with decimal representation equal to s by 1000000007 (109 + 7). When you represent s as a decimal number, please ignore the leading zeroes; also if s is an empty string, then it's assumed that the number equals to zero.

Andrew got tired of processing Eugene's requests manually and he asked you to write a program for that. Help him!

Input

The first line contains string s (1 ≤ |s| ≤ 105), consisting of digits — the string before processing all the requests.

The second line contains a single integer n (0 ≤ n ≤ 105) — the number of queries.

The next n lines contain the descriptions of the queries. The i-th query is described by string "di->ti", where di is exactly one digit (from 0 to 9), ti is a string consisting of digits (ti can be an empty string). The sum of lengths of ti for all queries doesn't exceed 105. The queries are written in the order in which they need to be performed.

Output

Print a single integer — remainder of division of the resulting number by 1000000007 (109 + 7).

Examples

Input

123123
1
2-&gt;00


Output

10031003


Input

123123
1
3-&gt;


Output

1212


Input

222
2
2-&gt;0
0-&gt;7


Output

777


Input

1000000008
0


Output

1

Note

Note that the leading zeroes are not removed from string s after the replacement (you can see it in the third sample).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day Vasya was sitting on a not so interesting Maths lesson and making an origami from a rectangular a mm  ×  b mm sheet of paper (a > b). Usually the first step in making an origami is making a square piece of paper from the rectangular sheet by folding the sheet along the bisector of the right angle, and cutting the excess part.

 [Image] 

After making a paper ship from the square piece, Vasya looked on the remaining (a - b) mm  ×  b mm strip of paper. He got the idea to use this strip of paper in the same way to make an origami, and then use the remainder (if it exists) and so on. At the moment when he is left with a square piece of paper, he will make the last ship from it and stop.

Can you determine how many ships Vasya will make during the lesson?


-----Input-----

The first line of the input contains two integers a, b (1 ≤ b < a ≤ 10^12) — the sizes of the original sheet of paper.


-----Output-----

Print a single integer — the number of ships that Vasya will make.


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

Output
2

Input
10 7

Output
6

Input
1000000000000 1

Output
1000000000000



-----Note-----

Pictures to the first and second sample test.

 [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day student Vasya was sitting on a lecture and mentioned a string s_1s_2... s_{n}, consisting of letters "a", "b" and "c" that was written on his desk. As the lecture was boring, Vasya decided to complete the picture by composing a graph G with the following properties:   G has exactly n vertices, numbered from 1 to n.  For all pairs of vertices i and j, where i ≠ j, there is an edge connecting them if and only if characters s_{i} and s_{j} are either equal or neighbouring in the alphabet. That is, letters in pairs "a"-"b" and "b"-"c" are neighbouring, while letters "a"-"c" are not. 

Vasya painted the resulting graph near the string and then erased the string. Next day Vasya's friend Petya came to a lecture and found some graph at his desk. He had heard of Vasya's adventure and now he wants to find out whether it could be the original graph G, painted by Vasya. In order to verify this, Petya needs to know whether there exists a string s, such that if Vasya used this s he would produce the given graph G.


-----Input-----

The first line of the input contains two integers n and m $(1 \leq n \leq 500,0 \leq m \leq \frac{n(n - 1)}{2})$ — the number of vertices and edges in the graph found by Petya, respectively.

Each of the next m lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — the edges of the graph G. It is guaranteed, that there are no multiple edges, that is any pair of vertexes appear in this list no more than once.


-----Output-----

In the first line print "Yes" (without the quotes), if the string s Petya is interested in really exists and "No" (without the quotes) otherwise.

If the string s exists, then print it on the second line of the output. The length of s must be exactly n, it must consist of only letters "a", "b" and "c" only, and the graph built using this string must coincide with G. If there are multiple possible answers, you may print any of them.


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

Output
Yes
aa

Input
4 3
1 2
1 3
1 4

Output
No



-----Note-----

In the first sample you are given a graph made of two vertices with an edge between them. So, these vertices can correspond to both the same and adjacent letters. Any of the following strings "aa", "ab", "ba", "bb", "bc", "cb", "cc" meets the graph's conditions. 

In the second sample the first vertex is connected to all three other vertices, but these three vertices are not connected with each other. That means that they must correspond to distinct letters that are not adjacent, but that is impossible as there are only two such letters: a and c.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kizahashi, who was appointed as the administrator of ABC at National Problem Workshop in the Kingdom of AtCoder, got too excited and took on too many jobs.
Let the current time be time 0. Kizahashi has N jobs numbered 1 to N.
It takes A_i units of time for Kizahashi to complete Job i. The deadline for Job i is time B_i, and he must complete the job before or at this time.
Kizahashi cannot work on two or more jobs simultaneously, but when he completes a job, he can start working on another immediately.
Can Kizahashi complete all the jobs in time? If he can, print Yes; if he cannot, print No.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N \leq 2 \times 10^5
 - 1 \leq A_i, B_i \leq 10^9 (1 \leq i \leq N)

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 B_1
.
.
.
A_N B_N

-----Output-----
If Kizahashi can complete all the jobs in time, print Yes; if he cannot, print No.

-----Sample Input-----
5
2 4
1 9
1 8
4 9
3 12

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

He can complete all the jobs in time by, for example, doing them in the following order:
 - Do Job 2 from time 0 to 1.
 - Do Job 1 from time 1 to 3.
 - Do Job 4 from time 3 to 7.
 - Do Job 3 from time 7 to 8.
 - Do Job 5 from time 8 to 11.
Note that it is fine to complete Job 3 exactly at the deadline, time 8.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given array *a* with *n* elements and the number *m*. Consider some subsequence of *a* and the value of least common multiple (LCM) of its elements. Denote LCM as *l*. Find any longest subsequence of *a* with the value *l*<=≤<=*m*.

A subsequence of *a* is an array we can get by erasing some elements of *a*. It is allowed to erase zero or all elements.

The LCM of an empty array equals 1.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=106) — the size of the array *a* and the parameter from the problem statement.

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

Output Specification:
In the first line print two integers *l* and *k**max* (1<=≤<=*l*<=≤<=*m*,<=0<=≤<=*k**max*<=≤<=*n*) — the value of LCM and the number of elements in optimal subsequence.

In the second line print *k**max* integers — the positions of the elements from the optimal subsequence in the ascending order.

Note that you can find and print any subsequence with the maximum length.

Demo Input:
['7 8\n6 2 9 2 7 2 3\n', '6 4\n2 2 2 3 3 3\n']

Demo Output:
['6 5\n1 2 4 6 7\n', '2 3\n1 2 3\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Igor has fallen in love with Tanya. Now Igor wants to show his feelings and write a number on the fence opposite to Tanya's house. Igor thinks that the larger the number is, the more chance to win Tanya's heart he has. 

Unfortunately, Igor could only get *v* liters of paint. He did the math and concluded that digit *d* requires *a**d* liters of paint. Besides, Igor heard that Tanya doesn't like zeroes. That's why Igor won't use them in his number.

Help Igor find the maximum number he can write on the fence.

Input Specification:
The first line contains a positive integer *v* (0<=≤<=*v*<=≤<=106). The second line contains nine positive integers *a*1,<=*a*2,<=...,<=*a*9 (1<=≤<=*a**i*<=≤<=105).

Output Specification:
Print the maximum number Igor can write on the fence. If he has too little paint for any digit (so, he cannot write anything), print -1.

Demo Input:
['5\n5 4 3 2 1 2 3 4 5\n', '2\n9 11 1 12 5 8 9 10 6\n', '0\n1 1 1 1 1 1 1 1 1\n']

Demo Output:
['55555\n', '33\n', '-1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Holidays have finished. Thanks to the help of the hacker Leha, Noora managed to enter the university of her dreams which is located in a town Pavlopolis. It's well known that universities provide students with dormitory for the period of university studies. Consequently Noora had to leave Vičkopolis and move to Pavlopolis. Thus Leha was left completely alone in a quiet town Vičkopolis. He almost even fell into a depression from boredom!

Leha came up with a task for himself to relax a little. He chooses two integers A and B and then calculates the greatest common divisor of integers "A factorial" and "B factorial". Formally the hacker wants to find out GCD(A!, B!). It's well known that the factorial of an integer x is a product of all positive integers less than or equal to x. Thus x! = 1·2·3·...·(x - 1)·x. For example 4! = 1·2·3·4 = 24. Recall that GCD(x, y) is the largest positive integer q that divides (without a remainder) both x and y.

Leha has learned how to solve this task very effective. You are able to cope with it not worse, aren't you?


-----Input-----

The first and single line contains two integers A and B (1 ≤ A, B ≤ 10^9, min(A, B) ≤ 12).


-----Output-----

Print a single integer denoting the greatest common divisor of integers A! and B!.


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

Output
6



-----Note-----

Consider the sample.

4! = 1·2·3·4 = 24. 3! = 1·2·3 = 6. The greatest common divisor of integers 24 and 6 is exactly 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer N. You need to convert all zeroes of N to 5. 
Example 1:
Input:
N = 1004
Output: 1554
Explanation: There are two zeroes in 1004
on replacing all zeroes with "5", the new
number will be "1554".
Example 2:
Input:
N = 121
Output: 121
Explanation: Since there are no zeroes in
"121", the number remains as "121".
Your Task:
Your task is to complete the function convertFive() which takes an integer N as an argument and replaces all zeros in the number N with 5. Your function should return the converted number.
Expected Time Complexity: O(K) where K is the number of digits in N
Expected Auxiliary Space: O(1)
Constraints:
1 <= n <= 10000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n cities in Berland. Some pairs of cities are connected by roads. All roads are bidirectional. Each road connects two different cities. There is at most one road between a pair of cities. The cities are numbered from 1 to n.

It is known that, from the capital (the city with the number 1), you can reach any other city by moving along the roads.

The President of Berland plans to improve the country's road network. The budget is enough to repair exactly n-1 roads. The President plans to choose a set of n-1 roads such that:

  * it is possible to travel from the capital to any other city along the n-1 chosen roads, 
  * if d_i is the number of roads needed to travel from the capital to city i, moving only along the n-1 chosen roads, then d_1 + d_2 + ... + d_n is minimized (i.e. as minimal as possible). 



In other words, the set of n-1 roads should preserve the connectivity of the country, and the sum of distances from city 1 to all cities should be minimized (where you can only use the n-1 chosen roads).

The president instructed the ministry to prepare k possible options to choose n-1 roads so that both conditions above are met.

Write a program that will find k possible ways to choose roads for repair. If there are fewer than k ways, then the program should output all possible valid ways to choose roads.

Input

The first line of the input contains integers n, m and k (2 ≤ n ≤ 2⋅10^5, n-1 ≤ m ≤ 2⋅10^5, 1 ≤ k ≤ 2⋅10^5), where n is the number of cities in the country, m is the number of roads and k is the number of options to choose a set of roads for repair. It is guaranteed that m ⋅ k ≤ 10^6.

The following m lines describe the roads, one road per line. Each line contains two integers a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i) — the numbers of the cities that the i-th road connects. There is at most one road between a pair of cities. The given set of roads is such that you can reach any city from the capital.

Output

Print t (1 ≤ t ≤ k) — the number of ways to choose a set of roads for repair. Recall that you need to find k different options; if there are fewer than k of them, then you need to find all possible different valid options.

In the following t lines, print the options, one per line. Print an option as a string of m characters where the j-th character is equal to '1' if the j-th road is included in the option, and is equal to '0' if the road is not included. The roads should be numbered according to their order in the input. The options can be printed in any order. All the t lines should be different.

Since it is guaranteed that m ⋅ k ≤ 10^6, the total length of all the t lines will not exceed 10^6.

If there are several answers, output any of them.

Examples

Input

4 4 3
1 2
2 3
1 4
4 3


Output

2
1110
1011


Input

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


Output

1
101001


Input

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


Output

2
111100
110110

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Welcome, ladies and gentlemen, to Aperture Science. Astronauts, War Heroes, Olympians — you’re here because we want the best, and you are it. That said, it’s time to make some science.

Now, I want each of you to stand on one of these buttons. Well done, we’re making great progress here. Now let’s do it again. Oh, come on - don’t stand on the same button! Move, people! No, no, that button’s only for the Astronauts, you know who you are. What?! You say you can’t do everything I ask? Ok let’s start over. You there, the Programmer, figure out how many times we can do this. And make it quick, we have a lot more science to get through…

-----Input-----
There will be a single test case in the input. The first line of this case will contain $n$ ($2 \le n \le 80$) giving the number of people (and the number of buttons) in the experiment. The next $n$ lines will contain $n$ characters each. If the $j^{th}$ character of the $i^{th}$ line is Y it indicates that the $i^{th}$ person can stand on the $j^{th}$ button (it is N otherwise).

-----Output-----
Output $k$, the maximum number of times everyone can be standing on buttons such that nobody stands on the same button more than once (This might be $0$). After that, output $k$ lines. Each line should contain $n$ integers separated by single spaces, where the $i^{th}$ integer describes which person is standing on the $i^{th}$ button. All of the lines should be valid and none of them should put the same person on the same button as a previous line of the same test case. Note that correct outputs might not be unique.

-----Examples-----
Sample Input:
3
YYY
NYY
YNY
Sample Output:
2
1 2 3
3 1 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an unsorted array arr[] of size N. Rotate the array to the left (counter-clockwise direction) by D steps, where D is a positive integer. 
 
Example 1:
Input:
N = 5, D = 2
arr[] = {1,2,3,4,5}
Output: 3 4 5 1 2
Explanation: 1 2 3 4 5  when rotated
by 2 elements, it becomes 3 4 5 1 2.
Example 2:
Input:
N = 10, D = 3
arr[] = {2,4,6,8,10,12,14,16,18,20}
Output: 8 10 12 14 16 18 20 2 4 6
Explanation: 2 4 6 8 10 12 14 16 18 20 
when rotated by 3 elements, it becomes 
8 10 12 14 16 18 20 2 4 6.
 
Your Task:
Complete the function rotateArr() which takes the array, D and N as input parameters and rotates the array by D elements. The array must be modified in-place without using extra space. 
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{6}
1 <= D <= 10^{6}
0 <= arr[i] <= 10^{5}

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