vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Marina loves strings of the same length and Vasya loves when there is a third string, different from them in exactly t characters. Help Vasya find at least one such string.

More formally, you are given two strings s_1, s_2 of length n and number t. Let's denote as f(a, b) the number of characters in which strings a and b are different. Then your task will be to find any string s_3 of length n, such that f(s_1, s_3) = f(s_2, s_3) = t. If there is no such string, print  - 1.


-----Input-----

The first line contains two integers n and t (1 ≤ n ≤ 10^5, 0 ≤ t ≤ n).

The second line contains string s_1 of length n, consisting of lowercase English letters.

The third line contain string s_2 of length n, consisting of lowercase English letters.


-----Output-----

Print a string of length n, differing from string s_1 and from s_2 in exactly t characters. Your string should consist only from lowercase English letters. If such string doesn't exist, print -1.


-----Examples-----
Input
3 2
abc
xyc

Output
ayd
Input
1 0
c
b

Output
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As we all know cultural fest of IIT-Delhi is one of the biggest youth festival of north india and this year too it was very special as there was live performance
by Arjit Singh.Now as he is very famous star in  india so there was a estimation of huge crowd and campus of IIT-Delhi may fail to handle such a crowd.
So,fest-management team of IIT-Delhi devised a solution by introducing tickets system.But this method failed due to huge demand of tickets suppose there were
n tickets(numbered 1 to n) that were sold out to watch Arjit Singh.So,in order to avoid mis-management due to huge crowd they re-invented a method that they will allow people to enter the arena in pairs.A pair will be selected such as the prime factorizaion of ticket number x and ticket number y has some fators in common 
and the product of common factor of x and y be M.Now a single ticket number x can be selected in  multiple pair.They are interested in only knowing number of
possible pair of enter the arena.They ask for you help as they are very busy in managing other activities of fest.

Your are given a number N denoting number of tickets sold out with each ticket having a distinct number from 1 to n.They also gives you an integer M denoting the product of common factors of any two ticket numbers and ask for how many pairs have such property. 

NOTE:-A particular ticket can be selected in multiple pairs.A number can be selected with him also so (x,x) is a valid pair.
A pair (x,y) is formed iff and only if x ≥ y.

Input Format:-

First line will contain an integer t denoting the number of test cases.
Each of next t lines contains two space integers N and M having usual meaning as described in question.

Output Format:-

For each test case output a single integer denoting the number of possible pair with common factor product as M.

**Constraints:-
1<t ≤ 100

1 ≤ N,M ≤ 1000000** 

SAMPLE INPUT
3
10 2
40 4
20 3

SAMPLE OUTPUT
10
32
12

Explanation

Test Case#1:-

ticket are numbered as 1,2,3,4,5,6,7,8,9,10 and we asked to give number of pair with  product of common factors as  2.The number of pairs are 10 since there are pairs which are

(2,2),(2,4),(2,6),(2,8),(2,10),(4,6),(4,10),(6,8),(6,10),(8,10)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a special linked list with N nodes where each node has a next pointer pointing to its next node. You are also given M random pointers, where you will be given M number of pairs denoting two nodes a and b  i.e. a->arb = b (arb is pointer to random node).
Construct a copy of the given list. The copy should consist of exactly N new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
For example, if there are two nodes X and Y in the original list, where X.arb --> Y, then for the corresponding two nodes x and y in the copied list, x.arb --> y.
Return the head of the copied linked list.
Note :- The diagram isn't part of any example, it just depicts an example of how the linked list may look like.
Example 1:
Input:
N = 4, M = 2
value = {1,2,3,4}
pairs = {{1,2},{2,4}}
Output: 1
Explanation: In this test case, there
are 4 nodes in linked list.  Among these
4 nodes,  2 nodes have arbitrary pointer
set, rest two nodes have arbitrary pointer
as NULL. Second line tells us the value
of four nodes. The third line gives the
information about arbitrary pointers.
The first node arbitrary pointer is set to
node 2.  The second node arbitrary pointer
is set to node 4.
Example 2:
Input:
N = 4, M = 2
value[] = {1,3,5,9}
pairs[] = {{1,1},{3,4}}
Output: 1
Explanation: In the given testcase ,
applying the method as stated in the
above example, the output will be 1.
Your Task:
The task is to complete the function copyList() which takes one argument the head of the linked list to be cloned and should return the head of the cloned linked list.
NOTE : 
1. If there is any node whose arbitrary pointer is not given then it's by default NULL. 
2. Your solution return an output 1 if your clone linked list is correct, else it returns 0.
3. Don't make any changes to the original linked list.
Expected Time Complexity : O(n)
Expected Auxilliary Space : O(1)
Constraints:
1 <= N <= 100
1 <= M <= N
1 <= a, b <= 100

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Anton likes to play chess. Also, he likes to do programming. That is why he decided to write the program that plays chess. However, he finds the game on 8 to 8 board to too simple, he uses an infinite one instead.

The first task he faced is to check whether the king is in check. Anton doesn't know how to implement this so he asks you to help.

Consider that an infinite chess board contains one white king and the number of black pieces. There are only rooks, bishops and queens, as the other pieces are not supported yet. The white king is said to be in check if at least one black piece can reach the cell with the king in one move. 

Help Anton and write the program that for the given position determines whether the white king is in check.

Remainder, on how do chess pieces move: 
 -  Bishop moves any number of cells diagonally, but it can't "leap" over the occupied cells. -  Rook moves any number of cells horizontally or vertically, but it also can't "leap" over the occupied cells. -  Queen is able to move any number of cells horizontally, vertically or diagonally, but it also can't "leap".

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=500<=000) — the number of black pieces.

The second line contains two integers *x*0 and *y*0 (<=-<=109<=≤<=*x*0,<=*y*0<=≤<=109) — coordinates of the white king.

Then follow *n* lines, each of them contains a character and two integers *x**i* and *y**i* (<=-<=109<=≤<=*x**i*,<=*y**i*<=≤<=109) — type of the *i*-th piece and its position. Character 'B' stands for the bishop, 'R' for the rook and 'Q' for the queen. It's guaranteed that no two pieces occupy the same position.

Output Specification:
The only line of the output should contains "YES" (without quotes) if the white king is in check and "NO" (without quotes) otherwise.

Demo Input:
['2\n4 2\nR 1 1\nB 1 5\n', '2\n4 2\nR 3 3\nB 1 5\n']

Demo Output:
['YES\n', 'NO\n']

Note:
Picture for the first sample: 

Picture for the second sample:

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problem statements in [Mandarin], [Vietnamese], and [Russian] as well.

Chef loves Chess and has thus invented a new piece named "Disabled King".

Let's denote the cell at the intersection of the i-th column from the left and j-th row from the top by (i, j).

If he is currently in cell (x,y), the disabled king can move to the following positions in one move (provided that he remains in the chessboard): 

(x,y+1)
(x,y-1)
(x+1,y+1)
(x+1,y-1)
(x-1,y+1)
(x-1,y-1)

In short, the Disabled King cannot move horizontally.

In an N \times N chessboard, the Disabled King is currently situated at the top-left corner (cell (1, 1)) and wants to reach the top-right corner (cell (N, 1)). Determine the minimum number of moves in which the task can be accomplished.

------ Input Format ------ 

- The first line will contain T, the number of test cases. Then the test cases follow.
- Each test case contains a single integer N in a separate line.

------ Output Format ------ 

Output the minimum number of moves to get from the top-left cell to the top-right one.

------ Constraints ------ 

$1 ≤ T ≤ 500$
$2 ≤ N ≤ 500$

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

----- Sample Output 1 ------ 
2
2

----- explanation 1 ------ 
Test case 1:

Initially chef is at $(1, 1)$. He cannot directly move to $(2, 1)$ as the disabled king cannot move horizontally. So he needs at least $2$ moves to reach $(2, 1)$. And that can be achieved by first moving to $(1, 2)$ and then moving to $(2, 1)$ from there.

Test case 2:

Clearly we cannot reach $(3, 1)$ from $(1, 1)$ in just one move. We require at least $2$ moves. And this can be achieved by first moving to $(2, 2)$ and then moving to $(3, 1)$ from there.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a weighted directed graph, consisting of n vertices and m edges. You should answer q queries of two types:

  * 1 v — find the length of shortest path from vertex 1 to vertex v. 
  * 2 c l1 l2 ... lc — add 1 to weights of edges with indices l1, l2, ..., lc. 

Input

The first line of input data contains integers n, m, q (1 ≤ n, m ≤ 105, 1 ≤ q ≤ 2000) — the number of vertices and edges in the graph, and the number of requests correspondingly.

Next m lines of input data contain the descriptions of edges: i-th of them contains description of edge with index i — three integers ai, bi, ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 109) — the beginning and the end of edge, and its initial weight correspondingly.

Next q lines of input data contain the description of edges in the format described above (1 ≤ v ≤ n, 1 ≤ lj ≤ m). It's guaranteed that inside single query all lj are distinct. Also, it's guaranteed that a total number of edges in all requests of the second type does not exceed 106.

Output

For each query of first type print the length of the shortest path from 1 to v in a separate line. Print -1, if such path does not exists.

Examples

Input

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


Output

1
0
2
1
4
2


Input

5 4 9
2 3 1
2 4 1
3 4 1
1 2 0
1 5
1 4
2 1 2
2 1 2
1 4
2 2 1 3
1 4
2 1 4
1 4


Output

-1
1
2
3
4

Note

The description of changes of the graph in the first sample case:

<image>

The description of changes of the graph in the second sample case:

<image>

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya works as a DJ in the best Berland nightclub, and he often uses dubstep music in his performance. Recently, he has decided to take a couple of old songs and make dubstep remixes from them.

Let's assume that a song consists of some number of words. To make the dubstep remix of this song, Vasya inserts a certain number of words "WUB" before the first word of the song (the number may be zero), after the last word (the number may be zero), and between words (at least one between any pair of neighbouring words), and then the boy glues together all the words, including "WUB", in one string and plays the song at the club.

For example, a song with words "I AM X" can transform into a dubstep remix as "WUBWUBIWUBAMWUBWUBX" and cannot transform into "WUBWUBIAMWUBX".

Recently, Petya has heard Vasya's new dubstep track, but since he isn't into modern music, he decided to find out what was the initial song that Vasya remixed. Help Petya restore the original song.

Input Specification:
The input consists of a single non-empty string, consisting only of uppercase English letters, the string's length doesn't exceed 200 characters. It is guaranteed that before Vasya remixed the song, no word contained substring "WUB" in it; Vasya didn't change the word order. It is also guaranteed that initially the song had at least one word.

Output Specification:
Print the words of the initial song that Vasya used to make a dubsteb remix. Separate the words with a space.

Demo Input:
['WUBWUBABCWUB\n', 'WUBWEWUBAREWUBWUBTHEWUBCHAMPIONSWUBMYWUBFRIENDWUB\n']

Demo Output:
['ABC ', 'WE ARE THE CHAMPIONS MY FRIEND ']

Note:
In the first sample: "WUBWUBABCWUB" = "WUB" + "WUB" + "ABC" + "WUB". That means that the song originally consisted of a single word "ABC", and all words "WUB" were added by Vasya.

In the second sample Vasya added a single word "WUB" between all neighbouring words, in the beginning and in the end, except for words "ARE" and "THE" — between them Vasya added two "WUB".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a string S consisting of lowercase English letters.
If the length of S is at most K, print S without change.
If the length of S exceeds K, extract the first K characters in S, append ... to the end of them, and print the result.

-----Constraints-----
 - K is an integer between 1 and 100 (inclusive).
 - S is a string consisting of lowercase English letters.
 - The length of S is between 1 and 100 (inclusive).

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

-----Output-----
Print a string as stated in Problem Statement.

-----Sample Input-----
7
nikoandsolstice

-----Sample Output-----
nikoand...

nikoandsolstice has a length of 15, which exceeds K=7.
We should extract the first 7 characters in this string, append ... to the end of them, and print the result nikoand....

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

Given a binary number, we are about to do some operations on the number. Two types of operations can be here:

* ['I', i, j] : Which means invert the bit from i to j (inclusive).

* ['Q', i] : Answer whether the i'th bit is 0 or 1.

The MSB (most significant bit) is the first bit (i.e. i = `1`). The binary number can contain leading zeroes.

## Example
```python
binary_simulation("0011001100", [['I', 1, 10], ['I', 2, 7], ['Q', 2], ['Q', 1], ['Q', 7], ['Q', 5]]) === [ '0', '1', '1', '0' ];
binary_simulation("1011110111", [['I', 1, 10], ['I', 2, 7], ['Q', 2], ['Q', 1], ['Q', 7], ['Q', 5]]) === [ '0', '0', '0', '1' ];
binary_simulation("1011110111", [['I', 1, 10], ['I', 2, 7]]) === [];
binary_simulation("0000000000", [['I', 1, 10], ['Q', 2]]) ===  ['1'];
```
## Note
* All inputs are valid.
* Please optimize your algorithm to avoid time out.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array a_0, a_1, ..., a_{N-1} of length N. Process Q queries of the following types.

The type of i-th query is represented by T_i.

* T_i=1: You are given two integers X_i,V_i. Replace the value of A_{X_i} with V_i.
* T_i=2: You are given two integers L_i,R_i. Calculate the maximum value among A_{L_i},A_{L_i+1},\cdots,A_{R_i}.
* T_i=3: You are given two integers X_i,V_i. Calculate the minimum j such that X_i \leq j \leq N, V_i \leq A_j. If there is no such j, answer j=N+1 instead.

Constraints

* 1 \leq N \leq 2 \times 10^5
* 0 \leq A_i \leq 10^9
* 1 \leq Q \leq 2 \times 10^5
* 1 \leq T_i \leq 3
* 1 \leq X_i \leq N, 0 \leq V_i \leq 10^9 (T_i=1,3)
* 1 \leq L_i \leq R_i \leq N (T_i=2)
* All values in Input are integer.

Input

Input is given from Standard Input in the following format:


N Q
A_1 A_2 \cdots A_N
First query
Second query
\vdots
Q-th query


Each query is given in the following format:

If T_i=1,3,


T_i X_i V_i


If T_i=2,


T_i L_i R_i


Output

For each query with T_i=2, 3, print the answer.

Example

Input

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


Output

3
3
2
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A zero-indexed array A of length N contains all integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], ... } subjected to the rule below.

Suppose the first element in S starts with the selection of element A[i] of index = i, the next element in S should be A[A[i]], and then A[A[A[i]]]… By that analogy, we stop adding right before a duplicate element occurs in S.

Example 1:

Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}


Note:

N is an integer within the range [1, 20,000].
The elements of A are all distinct.
Each element of A is an integer within the range [0, N-1].

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a sand trail in front of Alice's home.

In daytime, people walk over it and leave a footprint on the trail for their every single step. Alice cannot distinguish the order of the footprints, but she can tell whether each footprint is made by left foot or right foot. Also she's certain that all people are walking by alternating left foot and right foot.

For example, suppose that one person walked through the trail and left some footprints. The footprints are RRLRL in order along the trail ('R' means right foot and 'L' means left foot). You might think the outcome of the footprints is strange. But in fact, some steps are resulting from walking backwards!

There are some possible order of steps that produce these footprints such as 1 → 3 → 2 → 5 → 4 or 2 → 3 → 4 → 5 → 1 (we suppose that the distance between two consecutive steps can be arbitrarily long). The number of backward steps from above two examples are 2 and 1 separately.

Alice is interested in these footprints. Whenever there is a person walking trough the trail, she takes a picture of all these footprints along the trail and erase all of them so that next person will leave a new set of footprints. We know that people walk by alternating right foot and left foot, but we don't know if the first step is made by left foot or right foot.

Alice wants to know the minimum possible number of backward steps made by a person. But it's a little hard. Please help Alice to calculate it. You also need to construct one possible history of these footprints.

Input

Only one line containing the string S (1 ≤ |S| ≤ 100 000) containing all footprints in order along the trail from entrance to exit.

It is guaranteed that there is at least one possible footprint history.

Output

You should output 2 lines.

The first line should contain a number denoting the minimum number of backward steps.

The second line should contain a permutation of integers from 1 to |S|. This permutation should denote the order of footprints that may possible be used by person walked there.

If there are several possible answers, you may output any of them.

Examples

Input

RRLRL


Output

1
2 5 1 3 4


Input

RLRLRLRLR


Output

0
1 2 3 4 5 6 7 8 9


Input

RRRRRLLLL


Output

4
4 9 3 8 2 7 1 6 5

Note

For the first sample, one possible order is 2 → 5 → 1 → 3 → 4, among them only the step 5 → 1 is backward step so the answer is 1. 

For the second example one possible order is just to follow the order of input, thus there are no backward steps. 

For the third sample, there will be 4 backward steps because every step from L to R will be a backward step.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Just in case somebody missed it: this winter is totally cold in Nvodsk! It is so cold that one gets funny thoughts. For example, let's say there are strings with the length exactly *n*, based on the alphabet of size *m*. Any its substring with length equal to *k* is a palindrome. How many such strings exist? Your task is to find their quantity modulo 1000000007 (109<=+<=7). Be careful and don't miss a string or two!

Let us remind you that a string is a palindrome if it can be read the same way in either direction, from the left to the right and from the right to the left.

Input Specification:
The first and only line contains three integers: *n*, *m* and *k* (1<=≤<=*n*,<=*m*,<=*k*<=≤<=2000).

Output Specification:
Print a single integer — the number of strings of the described type modulo 1000000007 (109<=+<=7).

Demo Input:
['1 1 1\n', '5 2 4\n']

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

Note:
In the first sample only one string is valid: "a" (let's denote the only letter of our alphabet as "a").

In the second sample (if we denote the alphabet letters as "a" and "b") the following strings are valid: "aaaaa" and "bbbbb".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Luka started driving international routes with his truck. His biggest problem is the border with Slovenia. The border is a point of entrance into the European Union, so every truck is thoroughly examined. Because of this, Luka always has to wait several hours there. To kill the time, he comes up with various logic and math games.

In one of them, Luka first reads the numbers off of $N$ license plates and writes them down on a piece of paper. Then he tries to find an integer $M$ greater than $1$ such that all integers on the paper give the same remainder when divided by $M$. Luka tries to find as many such integers $M$ as possible.

Write a program that, given Luka’s $N$ integers, determines all such integers $M$.

-----Input-----
The first line contains the integer $N$ ($2 \le N \le 100$), the number of integers on paper. Each of the following $N$ lines contains one integer between $1$ and $1000000000$ (one billion). All these integers will be distinct. The input data will guarantee that at least one integer $M$ will always exist.

-----Output-----
Output all integers $M$ separated by spaces, in any order.

-----Examples-----
Sample Input:
3
6
34
38
Sample Output:
2 4

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