vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Leha plays a computer game, where is on each level is given a connected graph with n vertices and m edges. Graph can contain multiple edges, but can not contain self loops. Each vertex has an integer di, which can be equal to 0, 1 or  - 1. To pass the level, he needs to find a «good» subset of edges of the graph or say, that it doesn't exist. Subset is called «good», if by by leaving only edges from this subset in the original graph, we obtain the following: for every vertex i, di = - 1 or it's degree modulo 2 is equal to di. Leha wants to pass the game as soon as possible and ask you to help him. In case of multiple correct answers, print any of them.

Input

The first line contains two integers n, m (1 ≤ n ≤ 3·105, n - 1 ≤ m ≤ 3·105) — number of vertices and edges.

The second line contains n integers d1, d2, ..., dn ( - 1 ≤ di ≤ 1) — numbers on the vertices.

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n) — edges. It's guaranteed, that graph in the input is connected.

Output

Print  - 1 in a single line, if solution doesn't exist. Otherwise in the first line k — number of edges in a subset. In the next k lines indexes of edges. Edges are numerated in order as they are given in the input, starting from 1.

Examples

Input

1 0
1


Output

-1


Input

4 5
0 0 0 -1
1 2
2 3
3 4
1 4
2 4


Output

0


Input

2 1
1 1
1 2


Output

1
1


Input

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


Output

1
2

Note

In the first sample we have single vertex without edges. It's degree is 0 and we can not get 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Koa the Koala has a binary string $s$ of length $n$. Koa can perform no more than $n-1$ (possibly zero) operations of the following form:

In one operation Koa selects positions $i$ and $i+1$ for some $i$ with $1 \le i < |s|$ and sets $s_i$ to $max(s_i, s_{i+1})$. Then Koa deletes position $i+1$ from $s$ (after the removal, the remaining parts are concatenated).

Note that after every operation the length of $s$ decreases by $1$.

How many different binary strings can Koa obtain by doing no more than $n-1$ (possibly zero) operations modulo $10^9+7$ ($1000000007$)?


-----Input-----

The only line of input contains binary string $s$ ($1 \le |s| \le 10^6$). For all $i$ ($1 \le i \le |s|$) $s_i = 0$ or $s_i = 1$.


-----Output-----

On a single line print the answer to the problem modulo $10^9+7$ ($1000000007$).


-----Examples-----
Input
000

Output
3

Input
0101

Output
6

Input
0001111

Output
16

Input
00101100011100

Output
477



-----Note-----

In the first sample Koa can obtain binary strings: $0$, $00$ and $000$.

In the second sample Koa can obtain binary strings: $1$, $01$, $11$, $011$, $101$ and $0101$. For example:  to obtain $01$ from $0101$ Koa can operate as follows: $0101 \rightarrow 0(10)1 \rightarrow 011 \rightarrow 0(11) \rightarrow 01$.  to obtain $11$ from $0101$ Koa can operate as follows: $0101 \rightarrow (01)01 \rightarrow 101 \rightarrow 1(01) \rightarrow 11$. 

Parentheses denote the two positions Koa selected in each operation.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Astronaut Natasha arrived on Mars. She knows that the Martians are very poor aliens. To ensure a better life for the Mars citizens, their emperor decided to take tax from every tourist who visited the planet. Natasha is the inhabitant of Earth, therefore she had to pay the tax to enter the territory of Mars.

There are $n$ banknote denominations on Mars: the value of $i$-th banknote is $a_i$. Natasha has an infinite number of banknotes of each denomination.

Martians have $k$ fingers on their hands, so they use a number system with base $k$. In addition, the Martians consider the digit $d$ (in the number system with base $k$) divine. Thus, if the last digit in Natasha's tax amount written in the number system with the base $k$ is $d$, the Martians will be happy. Unfortunately, Natasha does not know the Martians' divine digit yet.

Determine for which values $d$ Natasha can make the Martians happy.

Natasha can use only her banknotes. Martians don't give her change.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le n \le 100\,000$, $2 \le k \le 100\,000$) — the number of denominations of banknotes and the base of the number system on Mars.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — denominations of banknotes on Mars.

All numbers are given in decimal notation.


-----Output-----

On the first line output the number of values $d$ for which Natasha can make the Martians happy.

In the second line, output all these values in increasing order.

Print all numbers in decimal notation.


-----Examples-----
Input
2 8
12 20

Output
2
0 4 
Input
3 10
10 20 30

Output
1
0 


-----Note-----

Consider the first test case. It uses the octal number system.

If you take one banknote with the value of $12$, you will get $14_8$ in octal system. The last digit is $4_8$.

If you take one banknote with the value of $12$ and one banknote with the value of $20$, the total value will be $32$. In the octal system, it is $40_8$. The last digit is $0_8$.

If you take two banknotes with the value of $20$, the total value will be $40$, this is $50_8$ in the octal system. The last digit is $0_8$.

No other digits other than $0_8$ and $4_8$ can be obtained. Digits $0_8$ and $4_8$ could also be obtained in other ways.

The second test case uses the decimal number system. The nominals of all banknotes end with zero, so Natasha can give the Martians only the amount whose decimal notation also ends with zero.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a dictionary $M$ that stores elements formed by a pair of a string key and an integer value, perform a sequence of the following operations. Note that each key in $M$ must be unique.

* insert($key$, $x$): Insert an element formed by a pair of $key$ and $x$ to $M$.
* get($key$): Print the value with the specified $key$. Print 0 if there is no such element.
* delete($key$): Delete the element with the specified $key$.

Constraints

* $1 \leq q \leq 200,000$
* $1 \leq x \leq 1,000,000,000$
* $1 \leq $ length of $key$ $ \leq 20$
* $key$ consits of lower case letters

Input

The input is given in the following format.


$q$
$query_1$
$query_2$
:
$query_q$


Each query $query_i$ is given by


0 $key$ $x$


or


1 $key$


or


2 $key$


where the first digits 0, 1 and 2 represent insert, get and delete operations respectively.

Output

For each get operation, print an integer in a line.

Example

Input

8
0 blue 4
0 red 1
0 white 5
1 red
1 blue
2 red
1 black
1 red


Output

1
4
0
0

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

Create a function that will return a string that combines all of the letters of the three inputed strings in groups.  Taking the first letter of all of the inputs and grouping them next to each other.  Do this for every letter, see example below!

**E.g. Input: "aa", "bb" , "cc" => Output: "abcabc"** 

*Note: You can expect all of the inputs to be the same length.*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are asked to ensure that the first and last names of people begin with a capital letter in their passports. For example, alison heck should be capitalised correctly as Alison Heck. 

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\$

Given a full name, your task is to capitalize the name appropriately.

Input Format

A single line of input containing the full name, $\mbox{S}$.

Constraints

$0<len(S)<1000$  
The string consists of alphanumeric characters and spaces.  

Note: in a word only the first character is capitalized. Example 12abc when capitalized remains 12abc. 

Output Format

Print the capitalized string, $\mbox{S}$.

Sample Input
chris alan

Sample Output
Chris Alan

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sam and his girl fiend went on a date. There is a sequence of numbers from 1 to 1000000. Sam picked a sub sequence SS and wants his friend to pick a number from SS. What is the probability that the number picked was a prime number.

Input Format

First Line of input contains T , number of test cases and next T lines contains L and R , the starting number and ending number of the sequence

Output Format

Print the answer with up to 6 digits after the decimal point.

Constraints

1 ≤ T ≤ 100000

1 ≤ L ≤ R ≤ 1000000
Register for IndiaHacksSAMPLE INPUT
2
1 10
3 3

SAMPLE OUTPUT
0.400000
1.000000

Register for IndiaHacks

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Barr the Bear is playing the game Bits with Swanky Shen!

Bits is a very simple game. At the start, a circle of $N$ non-negative integers $A_1$, $A_2$, $A_3$, $\ldots $, $A_ N$ is shown to both players. That is, to the left of the integer $A_ i$ is the integer $A_{i-1}$ if $i > 1$; and the integer $A_ N$ otherwise. To the right of the integer $A_ i$ is the integer $A_{i+1}$ if $i < N$; and the integer $A_1$ otherwise. Also an integer $K$ is given to both players.

To win this game, one must divide the circle of integers into exactly $K$ contiguous non-empty sections, such that the bitwise AND of the powers of all sections is maximized. The power of a contiguous section of integers is the bitwise OR of all integers in that section.

Barr the Bear is lazy and knows that you are wise with bits. Hence, he has hired you to help him to win the game!

Note: The binary bitwise operators OR and AND operate on the base-$2$ representation of the integers and correspond to the operators | and & respectively in C++ or Java.

-----Input-----
The first line contains integers $N$ and $K$ ($1 \leq K \leq N \leq 5\cdot 10^5$), namely the number of integers and the number of contiguous non-empty sections required.

The next line contains $N$ integers, the $i^\textrm {th}$ of which is the integer $A_ i$ ($0 \leq A_ i \leq 10^9$).

-----Output-----
Output a single integer in one line: The maximum bitwise AND of the powers of the sections in an optimal division of the circle of integers.

-----Explanation-----
In the first sample, the circle is $(2, 3, 4, 1)$. A possible division is $(3, 4)$ and $(1, 2)$. $(3, 4)$ has power $7$ and $(1, 2)$ has power $3$. The bitwise AND of $7$ and $3$ is $3$. Note that a section can possibly wrap around the circle.

In the second sample, a possible division is $(2, 2, 4)$, $(4)$, $(4, 2)$. The sections’ powers are $6$, $4$ and $6$ respectively, which have bitwise AND of $4$. Note that we require the sections to be contiguous integers, so the division $(2, 4)$, $(2, 4)$, $(2, 4)$ is not permissible.

In the third sample, we can only have one section. This section will have all the integers, and thus have power $3$.

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

Sample Input 2:
6 3
2 2 2 4 4 4
Sample Output 2:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n cards of different colours placed in a line, each of them can be either red, green or blue cards. Count the minimum number of cards to withdraw from the line so that no two adjacent cards have the same colour.

-----Input-----
- The first line of each input contains an integer n— the total number of cards.
- The next line of the input contains a string s, which represents the colours of the cards. We'll consider the cards in a line numbered from 1 to n from left to right. Then the $i^t$$^h$ alphabet equals "G", if the $i^t$$^h$ card is green, "R" if the card is red,  and "B", if it's blue.

-----Output-----
- Print a single integer — the answer to the problem.

-----Constraints-----
- $1 \leq n \leq 50$

-----Sample Input 1:-----
5
RGGBG

-----Sample Input 2:-----
5
RRRRR

-----Sample Input 3:-----
2
BB

-----Sample Output 1:-----
1

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

-----Sample Output 3:-----
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three integers $a$, $b$ and $x$. Your task is to construct a binary string $s$ of length $n = a + b$ such that there are exactly $a$ zeroes, exactly $b$ ones and exactly $x$ indices $i$ (where $1 \le i < n$) such that $s_i \ne s_{i + 1}$. It is guaranteed that the answer always exists.

For example, for the string "01010" there are four indices $i$ such that $1 \le i < n$ and $s_i \ne s_{i + 1}$ ($i = 1, 2, 3, 4$). For the string "111001" there are two such indices $i$ ($i = 3, 5$).

Recall that binary string is a non-empty sequence of characters where each character is either 0 or 1.


-----Input-----

The first line of the input contains three integers $a$, $b$ and $x$ ($1 \le a, b \le 100, 1 \le x < a + b)$.


-----Output-----

Print only one string $s$, where $s$ is any binary string satisfying conditions described above. It is guaranteed that the answer always exists.


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

Output
1100

Input
3 3 3

Output
101100

Input
5 3 6

Output
01010100



-----Note-----

All possible answers for the first example:   1100;  0011. 

All possible answers for the second example:   110100;  101100;  110010;  100110;  011001;  001101;  010011;  001011.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarpus likes studying at school a lot and he is always diligent about his homework. Polycarpus has never had any problems with natural sciences as his great-great-grandfather was the great physicist Seinstein. On the other hand though, Polycarpus has never had an easy time with history.

Everybody knows that the World history encompasses exactly *n* events: the *i*-th event had continued from the year *a**i* to the year *b**i* inclusive (*a**i*<=&lt;<=*b**i*). Polycarpus easily learned the dates when each of *n* events started and ended (Polycarpus inherited excellent memory from his great-great-granddad). But the teacher gave him a more complicated task: Polycaprus should know when all events began and ended and he should also find out for each event whether it includes another event. Polycarpus' teacher thinks that an event *j* includes an event *i* if *a**j*<=&lt;<=*a**i* and *b**i*<=&lt;<=*b**j*. Your task is simpler: find the number of events that are included in some other event.

Input Specification:
The first input line contains integer *n* (1<=≤<=*n*<=≤<=105) which represents the number of events. Next *n* lines contain descriptions of the historical events, one event per line. The *i*<=+<=1 line contains two integers *a**i* and *b**i* (1<=≤<=*a**i*<=&lt;<=*b**i*<=≤<=109) — the beginning and the end of the *i*-th event. No two events start or finish in the same year, that is, *a**i*<=≠<=*a**j*,<=*a**i*<=≠<=*b**j*,<=*b**i*<=≠<=*a**j*,<=*b**i*<=≠<=*b**j* for all *i*, *j* (where *i*<=≠<=*j*). Events are given in arbitrary order.

Output Specification:
Print the only integer — the answer to the problem.

Demo Input:
['5\n1 10\n2 9\n3 8\n4 7\n5 6\n', '5\n1 100\n2 50\n51 99\n52 98\n10 60\n', '1\n1 1000000000\n']

Demo Output:
['4\n', '4\n', '0\n']

Note:
In the first example the fifth event is contained in the fourth. Similarly, the fourth event is contained in the third, the third — in the second and the second — in the first.

In the second example all events except the first one are contained in the first.

In the third example only one event, so the answer is 0.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a sequence *a* consisting of *n* integers. Find the maximum possible value of  (integer remainder of *a**i* divided by *a**j*), where 1<=≤<=*i*,<=*j*<=≤<=*n* and *a**i*<=≥<=*a**j*.

Input Specification:
The first line contains integer *n* — the length of the sequence (1<=≤<=*n*<=≤<=2·105). 

The second line contains *n* space-separated integers *a**i* (1<=≤<=*a**i*<=≤<=106).

Output Specification:
Print the answer to the problem.

Demo Input:
['3\n3 4 5\n']

Demo Output:
['2\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Problem Statement
As they say, small is cute and beautiful.

Given N distinct positive integers, find the smallest number that can be formed by concatenating all of them.
Input Format
The first line of the input file contains a positive integer N. Then N lines follow.
Each line contains a single positive integer K.

Output Format
Output the smallest possible number that can be formed by concatenating all the numbers.

Constraints
1 ≤ N ≤ 5000
1 ≤ K ≤ 10^15

SAMPLE INPUT
5
14
66
907
1234567890
9876543210

SAMPLE OUTPUT
123456789014669079876543210

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Learning about all the sinusoidal functions of trigonometry, Rahul has grown fond of numbers, whose digits increase and decrease alternatively.  

Let's call d[i] is the i^th digit of a number d. Formally, a wavy number is defined as a number d such that either d[0] < d[1] > d[2] ... or d[0] > d[1] < d[2] ...  

Given a number N, can you find the integers L and R such that the range [L, N] and [N, R] each contain exactly K wavy numbers. Also, these ranges should be as large as possible.

Note that if no L ≥ 1 is found or the required value of R exceeds 10^18, you should output -1.

Input:
The first line of input file contains T, the number of test cases to follow.
Each of the following T lines contain two space-separated integers N and K.

Output:
Output exactly T lines, each containing two integers L and R sepated by a single space.

Constraints:
1 ≤ T ≤ 625
1 ≤ K, N ≤ 10^18

SAMPLE INPUT
2
9 2
2 3

SAMPLE OUTPUT
8 11
-1 4

Explanation

Case 1:
[8, 9] has 2 wavy numbers 8 and 9.
[9, 11] has 2 wavy numbers 8 and 10. Note that [9, 10] also has 2 wavy numbers but its size is not maximal.

Case 2:
Note that for no value of L ≥ 1 we can have a range that has 3 wavy numbers and the range ends at 2. So, value of L is -1. R is simply 4 as [2, 4] contains 3 wavy numbers 2, 3 and 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Scientists working internationally use metric units almost exclusively. Unless that is, they wish to crash multimillion dollars worth of equipment on Mars.

Your task is to write a simple function that takes a number of meters, and outputs it using metric prefixes.

In practice, meters are only measured in "mm" (thousandths of a meter), "cm" (hundredths of a meter), "m" (meters) and "km" (kilometers, or clicks for the US military).

For this exercise we just want units bigger than a meter, from meters up to yottameters, excluding decameters and hectometers.

All values passed in will be positive integers.
e.g.

```python
meters(5);
// returns "5m"

meters(51500);
// returns "51.5km"

meters(5000000);
// returns "5Mm"
```

See http://en.wikipedia.org/wiki/SI_prefix for a full list of prefixes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between the easy and the hard version is the constraint on $n$.

You are given an undirected complete graph on $n$ vertices. A complete graph is a graph where each pair of vertices is connected by an edge. You have to paint the edges of the graph into two colors, red and blue (each edge will have one color).

A set of vertices $S$ is red-connected if, for every pair of vertices $(v_1, v_2)$ such that $v_1 \in S$ and $v_2 \in S$, there exists a path from $v_1$ to $v_2$ that goes only through red edges and vertices from $S$. Similarly, a set of vertices $S$ is blue-connected if, for every pair of vertices $(v_1, v_2)$ such that $v_1 \in S$ and $v_2 \in S$, there exists a path from $v_1$ to $v_2$ that goes only through blue edges and vertices from $S$.

You have to paint the graph in such a way that:

there is at least one red edge;

there is at least one blue edge;

for each set of vertices $S$ such that $|S| \ge 2$, $S$ is either red-connected or blue-connected, but not both.

Calculate the number of ways to paint the graph, and print it modulo $998244353$.


-----Input-----

The first (and only) line contains one integer $n$ ($3 \le n \le 5 \cdot 10^3$).


-----Output-----

Print one integer — the number of ways to paint the graph, taken modulo $998244353$.


-----Examples-----

Input
3
Output
6
Input
4
Output
50
Input
100
Output
878752271
Input
1337
Output
520628749


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ujan has been lazy lately, but now has decided to bring his yard to good shape. First, he decided to paint the path from his house to the gate.

The path consists of $n$ consecutive tiles, numbered from $1$ to $n$. Ujan will paint each tile in some color. He will consider the path aesthetic if for any two different tiles with numbers $i$ and $j$, such that $|j - i|$ is a divisor of $n$ greater than $1$, they have the same color. Formally, the colors of two tiles with numbers $i$ and $j$ should be the same if $|i-j| > 1$ and $n \bmod |i-j| = 0$ (where $x \bmod y$ is the remainder when dividing $x$ by $y$).

Ujan wants to brighten up space. What is the maximum number of different colors that Ujan can use, so that the path is aesthetic?


-----Input-----

The first line of input contains a single integer $n$ ($1 \leq n \leq 10^{12}$), the length of the path.


-----Output-----

Output a single integer, the maximum possible number of colors that the path can be painted in.


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

Output
2

Input
5

Output
5



-----Note-----

In the first sample, two colors is the maximum number. Tiles $1$ and $3$ should have the same color since $4 \bmod |3-1| = 0$. Also, tiles $2$ and $4$ should have the same color since $4 \bmod |4-2| = 0$.

In the second sample, all five colors can be used. [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The numbers of all offices in the new building of the Tax Office of IT City will have lucky numbers.

Lucky number is a number that consists of digits 7 and 8 only. Find the maximum number of offices in the new building of the Tax Office given that a door-plate can hold a number not longer than n digits.


-----Input-----

The only line of input contains one integer n (1 ≤ n ≤ 55) — the maximum length of a number that a door-plate can hold.


-----Output-----

Output one integer — the maximum number of offices, than can have unique lucky numbers not longer than n digits.


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

Output
6

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