vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
We often have to copy large volumes of information. Such operation can take up many computer resources. Therefore, in this problem you are advised to come up with a way to copy some part of a number array into another one, quickly.

More formally, you've got two arrays of integers a_1, a_2, ..., a_{n} and b_1, b_2, ..., b_{n} of length n. Also, you've got m queries of two types:  Copy the subsegment of array a of length k, starting from position x, into array b, starting from position y, that is, execute b_{y} + q = a_{x} + q for all integer q (0 ≤ q < k). The given operation is correct — both subsegments do not touch unexistent elements.  Determine the value in position x of array b, that is, find value b_{x}. 

For each query of the second type print the result — the value of the corresponding element of array b.


-----Input-----

The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 10^5) — the number of elements in the arrays and the number of queries, correspondingly. The second line contains an array of integers a_1, a_2, ..., a_{n} (|a_{i}| ≤ 10^9). The third line contains an array of integers b_1, b_2, ..., b_{n} (|b_{i}| ≤ 10^9).

Next m lines contain the descriptions of the queries. The i-th line first contains integer t_{i} — the type of the i-th query (1 ≤ t_{i} ≤ 2). If t_{i} = 1, then the i-th query means the copying operation. If t_{i} = 2, then the i-th query means taking the value in array b. If t_{i} = 1, then the query type is followed by three integers x_{i}, y_{i}, k_{i} (1 ≤ x_{i}, y_{i}, k_{i} ≤ n) — the parameters of the copying query. If t_{i} = 2, then the query type is followed by integer x_{i} (1 ≤ x_{i} ≤ n) — the position in array b.

All numbers in the lines are separated with single spaces. It is guaranteed that all the queries are correct, that is, the copying borders fit into the borders of arrays a and b.


-----Output-----

For each second type query print the result on a single line.


-----Examples-----
Input
5 10
1 2 0 -1 3
3 1 5 -2 0
2 5
1 3 3 3
2 5
2 4
2 1
1 2 1 4
2 1
2 4
1 4 2 1
2 2

Output
0
3
-1
3
2
3
-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A tree is an undirected connected graph without cycles.

Let's consider a rooted undirected tree with n vertices, numbered 1 through n. There are many ways to represent such a tree. One way is to create an array with n integers p1, p2, ..., pn, where pi denotes a parent of vertex i (here, for convenience a root is considered its own parent).

<image> For this rooted tree the array p is [2, 3, 3, 2].

Given a sequence p1, p2, ..., pn, one is able to restore a tree:

  1. There must be exactly one index r that pr = r. A vertex r is a root of the tree. 
  2. For all other n - 1 vertices i, there is an edge between vertex i and vertex pi. 



A sequence p1, p2, ..., pn is called valid if the described procedure generates some (any) rooted tree. For example, for n = 3 sequences (1,2,2), (2,3,1) and (2,1,3) are not valid.

You are given a sequence a1, a2, ..., an, not necessarily valid. Your task is to change the minimum number of elements, in order to get a valid sequence. Print the minimum number of changes and an example of a valid sequence after that number of changes. If there are many valid sequences achievable in the minimum number of changes, print any of them.

Input

The first line of the input contains an integer n (2 ≤ n ≤ 200 000) — the number of vertices in the tree.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ n).

Output

In the first line print the minimum number of elements to change, in order to get a valid sequence.

In the second line, print any valid sequence possible to get from (a1, a2, ..., an) in the minimum number of changes. If there are many such sequences, any of them will be accepted.

Examples

Input

4
2 3 3 4


Output

1
2 3 4 4 


Input

5
3 2 2 5 3


Output

0
3 2 2 5 3 


Input

8
2 3 5 4 1 6 6 7


Output

2
2 3 7 8 1 6 6 7

Note

In the first sample, it's enough to change one element. In the provided output, a sequence represents a tree rooted in a vertex 4 (because p4 = 4), which you can see on the left drawing below. One of other correct solutions would be a sequence 2 3 3 2, representing a tree rooted in vertex 3 (right drawing below). On both drawings, roots are painted red.

<image>

In the second sample, the given sequence is already valid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: MUH and House of Cards

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polar bears Menshykov and Uslada from the zoo of St. Petersburg and elephant Horace from the zoo of Kiev decided to build a house of cards. For that they've already found a hefty deck of *n* playing cards. Let's describe the house they want to make: 
 1.  The house consists of some non-zero number of floors. 1.  Each floor consists of a non-zero number of rooms and the ceiling. A room is two cards that are leaned towards each other. The rooms are made in a row, each two adjoining rooms share a ceiling made by another card. 1.  Each floor besides for the lowest one should contain less rooms than the floor below. 
Please note that the house may end by the floor with more than one room, and in this case they also must be covered by the ceiling. Also, the number of rooms on the adjoining floors doesn't have to differ by one, the difference may be more. 

While bears are practicing to put cards, Horace tries to figure out how many floors their house should consist of. The height of the house is the number of floors in it. It is possible that you can make a lot of different houses of different heights out of *n* cards. It seems that the elephant cannot solve this problem and he asks you to count the number of the distinct heights of the houses that they can make using exactly *n* cards.

Input Specification:
The single line contains integer *n* (1<=≤<=*n*<=≤<=1012) — the number of cards.

Output Specification:
Print the number of distinct heights that the houses made of exactly *n* cards can have.

Demo Input:
['13\n', '6\n']

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

Note:
In the first sample you can build only these two houses (remember, you must use all the cards):

Thus, 13 cards are enough only for two floor houses, so the answer is 1.

The six cards in the second sample are not enough to build any house.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string $s$, consisting only of characters '0' and '1'.

You have to choose a contiguous substring of $s$ and remove all occurrences of the character, which is a strict minority in it, from the substring.

That is, if the amount of '0's in the substring is strictly smaller than the amount of '1's, remove all occurrences of '0' from the substring. If the amount of '1's is strictly smaller than the amount of '0's, remove all occurrences of '1'. If the amounts are the same, do nothing.

You have to apply the operation exactly once. What is the maximum amount of characters that can be removed?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The only line of each testcase contains a non-empty string $s$, consisting only of characters '0' and '1'. The length of $s$ doesn't exceed $2 \cdot 10^5$.

The total length of strings $s$ over all testcases doesn't exceed $2 \cdot 10^5$.


-----Output-----

For each testcase, print a single integer — the maximum amount of characters that can be removed after applying the operation exactly once.


-----Examples-----

Input
4
01
1010101010111
00110001000
1
Output
0
5
3
0


-----Note-----

In the first testcase, you can choose substrings "0", "1" or "01". In "0" the amount of '0' is $1$, the amount of '1' is $0$. '1' is a strict minority, thus all occurrences of it are removed from the substring. However, since there were $0$ of them, nothing changes. Same for "1". And in "01" neither of '0' or '1' is a strict minority. Thus, nothing changes. So there is no way to remove any characters.

In the second testcase, you can choose substring "10101010101". It contains $5$ characters '0' and $6$ characters '1'. '0' is a strict minority. Thus, you can remove all its occurrences. There exist other substrings that produce the same answer.

In the third testcase, you can choose substring "011000100". It contains $6$ characters '0' and $3$ characters '1'. '1' is a strict minority. Thus, you can remove all its occurrences.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array where each element is the money a person have and there is only Rs. 3 note. We need to check whether it is possible to divide the money equally among all the persons or not. If it is possible then find Minimum number of transactions needed.
 
Example 1:
Input: nums = [5, 8, 11]
Output: 1
Explanation: 3rd person can give Rs. 3
then all person would have Rs. 8
Example 2:
Input: nums = [1, 2, 3, 4]
Output: -1
Explanation: 1 + 2 + 3 + 4 = 10. Rs. 10 
can not be distributed among 4 persons.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function MinimumTransaction() which takes the array as input parameter and returns the minimum number of transactions needed to distribute the money equally. If not possible returns -1.
 
Expected Time Complexity: O(n) where n is length of array
Expected Space Complexity: O(1)
 
Constraints:
1 <= n <= 10^{5}
1 <= elements of array <= 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Implement a function which 
creates a **[radix tree](https://en.wikipedia.org/wiki/Radix_tree)** (a space-optimized trie [prefix tree]) 
in which each node that is the only child is merged with its parent [unless a word from the input ends there]) 
from a given list of words 
using dictionaries (aka hash maps or hash tables) where:

1. The dictionary keys are the nodes.
2. Leaf nodes are empty dictionaries.
3. The value for empty input is an empty dictionary.
4. Words are all lowercase or empty strings.
5. Words can contain duplicates.

### Examples:

```python
>>> radix_tree()
{}

>>> radix_tree("")
{}

>>> radix_tree("", "")
{}

>>> radix_tree("radix", "tree")
{"radix": {}, "tree": {}}

>>> radix_tree("ape", "apple")
{"ap": {"e": {}, "ple": {}}}

>>> radix_tree("apple", "applet", "apple", "ape")
{"ap": {"ple": {"t": {}}, "e": {}}}

>>> radix_tree("romane", "romanus", "romulus", "rubens", "rubicon", "rubicundus")
{"r": {"om": {"an": {"e": {}, "us": {}}, "ulus": {}},
       "ub": {"ens": {}, "ic": {"on": {}, "undus": {}}}}}

>>> radix_tree("appleabcd", "apple")
{"apple": {"abcd": {}}}
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array of integers. Your task is to sort odd numbers within the array in ascending order, and even numbers in descending order.

Note that zero is an even number. If you have an empty array, you need to return it.


For example:
```
[5, 3, 2, 8, 1, 4]  -->  [1, 3, 8, 4, 5, 2]

odd numbers ascending:   [1, 3,       5   ]
even numbers descending: [      8, 4,    2]
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two kingdoms had been at war for a long time, until the emperor intervened to bring an end to the conflict. The territory in question comprises an $M$ by $N$ rectangular grid. At the emperor’s insistence, the two kings have withdrawn their troops until no two opposing troops are in adjacent squares of the map (adjacent being horizontal or vertical – diagonal is not considered).

The emperor proposes to designate certain squares of the map as neutral territory. Neither king will be allowed to move troops into those squares, and the emperor’s own forces will patrol them to be sure that both kings observe these rules.

The emperor is frugal and does not want to commit more soldiers to this effort than absolutely necessary. His generals have marked each square of the map with the number of soldiers required to secure that square. What remains is to choose which of those squares should be patrolled.

Write a program to determine the minimum number of soldiers that the emperor will need to be deploy to guarantee that the troops of one kingdom cannot move, in one or more steps, into squares occupied by the troops of the second kingdom (moving horizontally or vertically) without encountering the emperor’s own soldiers.

-----Input-----
Input begins with a line containing $2$ integers, $w$ and $h$, denoting the width and height of the map, where $1 \leq w, h \leq 40$.

This is followed by $h$ lines. Each line contains $w$ characters, left justified. These characters will be ‘A’ or ‘B’, designating a position held by king A or king B, or a single numeric digit, designating a currently unoccupied position that can be secured by the use of that number of soldiers. For example, a ‘2’ would indicate that two soldiers must be deployed to that square to secure it against passage of other troops. A ‘0’ indicates terrain that is impassible – the emperor need not commit soldiers there because the kingdom troops cannot pass through that square.

No ‘A’ will be adjacent, horizontally or vertically, to any ‘B’.

There will be at least one ‘A’ and one ‘B’ in the input.

-----Output-----
Print a single line containing an integer denoting the minimum number of soldiers that the emperor must deploy to guarantee that there is no open path between any ‘A’ position and any ‘B’ position, using any combination of horizontal or vertical moves.

-----Examples-----
Sample Input:
8 5
A11111AA
AA7B111A
111BB111
11BBB111
11BBB11B
Sample Output:
13

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There is a fence in front of Polycarpus's home. The fence consists of *n* planks of the same width which go one after another from left to right. The height of the *i*-th plank is *h**i* meters, distinct planks can have distinct heights.

Polycarpus has bought a posh piano and is thinking about how to get it into the house. In order to carry out his plan, he needs to take exactly *k* consecutive planks from the fence. Higher planks are harder to tear off the fence, so Polycarpus wants to find such *k* consecutive planks that the sum of their heights is minimal possible.

Write the program that finds the indexes of *k* consecutive planks with minimal total height. Pay attention, the fence is not around Polycarpus's home, it is in front of home (in other words, the fence isn't cyclic).

Input Specification:
The first line of the input contains integers *n* and *k* (1<=≤<=*n*<=≤<=1.5·105,<=1<=≤<=*k*<=≤<=*n*) — the number of planks in the fence and the width of the hole for the piano. The second line contains the sequence of integers *h*1,<=*h*2,<=...,<=*h**n* (1<=≤<=*h**i*<=≤<=100), where *h**i* is the height of the *i*-th plank of the fence.

Output Specification:
Print such integer *j* that the sum of the heights of planks *j*, *j*<=+<=1, ..., *j*<=+<=*k*<=-<=1 is the minimum possible. If there are multiple such *j*'s, print any of them.

Demo Input:
['7 3\n1 2 6 1 1 7 1\n']

Demo Output:
['3\n']

Note:
In the sample, your task is to find three consecutive planks with the minimum sum of heights. In the given case three planks with indexes 3, 4 and 5 have the required attribute, their total height is 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The longest common prefix of two words is the longest word that both words start with. For example, the longest common prefix of the words “identity” and “idealistic” is the word “ide”. A database contains $N$ words.

The algorithm to search for a query word $W$ in the database is primitive. It compares the word $W$ one by one with each word in the database. Two words are compared letter by letter until a letter in which they differ is found or until the end of one of the words is reached (it is then established either that the words are equal or that one is longer than the other). When the algorithm finds the word $W$ in the database, it terminates.

Analysing the algorithm shows that the number of steps needed to find a word $W$ is equal to the number of words $W$ is compared to, plus the sum of the lengths of the longest common prefixes of W and each of the words it was compared to.

Write a program that calculates the number of steps the algorithm uses to find each of the $Q$ query words.

-----Input-----
The first line contains an integer $N$ $(1 \leq N \leq 30000)$, the number of words in the database. Each of the following $N$ lines contains a single word from the database. The words are given in the order the algorithm compares them to a query word. All words in the database will be distinct. The following line contains an integer $Q$ $(1 \leq Q \leq 30000)$, the number of words searched for. Each of the following $Q$ lines contains a single query word.

All words in the input will be strings of less than $30$ lowercase letters of the English alphabet

-----Output-----
Output one integer per line for each query word, the number of steps the algorithm uses when searching for the word.

-----Examples-----
Sample Input:
5
hobotnica
robot
hobi
hobit
robi
4
robi
hobi
hobit
rakija
Sample Output:
12
10
16
7

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

Write a method that takes an array of consecutive (increasing) letters as input and that returns the missing letter in the array.

You will always get an valid array. And it will be always exactly one letter be missing. The length of the array will always be at least 2.
The array will always contain letters in only one case.

Example:
```if-not:swift
['a','b','c','d','f'] -> 'e'
['O','Q','R','S'] -> 'P'
```

(Use the English alphabet with 26 letters!)

Have fun coding it and please don't forget to vote and rank this kata! :-) 

I have also created other katas. Take a look if you enjoyed this kata!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Finally, a basketball court has been opened in SIS, so Demid has decided to hold a basketball exercise session. $2 \cdot n$ students have come to Demid's exercise session, and he lined up them into two rows of the same size (there are exactly $n$ people in each row). Students are numbered from $1$ to $n$ in each row in order from left to right.

 [Image] 

Now Demid wants to choose a team to play basketball. He will choose players from left to right, and the index of each chosen player (excluding the first one taken) will be strictly greater than the index of the previously chosen player. To avoid giving preference to one of the rows, Demid chooses students in such a way that no consecutive chosen students belong to the same row. The first student can be chosen among all $2n$ students (there are no additional constraints), and a team can consist of any number of students. 

Demid thinks, that in order to compose a perfect team, he should choose students in such a way, that the total height of all chosen students is maximum possible. Help Demid to find the maximum possible total height of players in a team he can choose.


-----Input-----

The first line of the input contains a single integer $n$ ($1 \le n \le 10^5$) — the number of students in each row.

The second line of the input contains $n$ integers $h_{1, 1}, h_{1, 2}, \ldots, h_{1, n}$ ($1 \le h_{1, i} \le 10^9$), where $h_{1, i}$ is the height of the $i$-th student in the first row.

The third line of the input contains $n$ integers $h_{2, 1}, h_{2, 2}, \ldots, h_{2, n}$ ($1 \le h_{2, i} \le 10^9$), where $h_{2, i}$ is the height of the $i$-th student in the second row.


-----Output-----

Print a single integer — the maximum possible total height of players in a team Demid can choose.


-----Examples-----
Input
5
9 3 5 7 3
5 8 1 4 5

Output
29

Input
3
1 2 9
10 1 1

Output
19

Input
1
7
4

Output
7



-----Note-----

In the first example Demid can choose the following team as follows:  [Image] 

In the second example Demid can choose the following team as follows:  [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Oz has a list arr[] of M integers. He has to find all integers K such that :

1) K > 1
2) arr[1]%K = arr[2]%K = arr[3]%K = ... = arr[M]%K where '%' is a modulus operator

Help Oz to find all such K's.

Input :
First line of input contains an integer M. Then M lines follow each containing one integer of the list. Input data is such that at least one integer K will always exist. 

Output :
Output all possible integers K separated by space in increasing order.

Constraints :
 - 2 ≤ M ≤100
 - 1< value of each integer <10^9
 - All integers will be distinct

SAMPLE INPUT
3
38
6
34

SAMPLE OUTPUT
2 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Once N boys and M girls attended a party. You are given a matrix A of N rows and M columns where Aij is 1 if the i-th boy likes the j-th girl, otherwise it will be 0. Note that it is not necessary that if a boy x likes girl y, then girl y should like boy x.
You know that if there are two different boys x and y, who both like girl z, then there will be a collision.
Can you calculate the number of different collisions at this party? Note that order of boys in the collision doesn't matter.

-----Input-----
The first line contains a single integer T denoting the number of test cases. Then T test cases follow.
The first line of each test case contains two space separated integers N, M denoting the number of boys and girls, respectively.
Each of the following N lines contain M characters, each of them is either '0' or '1'.

-----Output-----
For each test case output a single line containing an integer corresponding to the number of collisions at the party.

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ N, M ≤ 10

-----Example-----
Input:
2
4 3
111
100
110
000
2 2
10
01

Output:
4
0

-----Explanation-----
Example Case 1. All three boys like the first girl, so there are (1, 2, 1), (1, 3, 1), (2, 3, 1) collisions with her. Boys 1 and 3 both like the second girl so this is one more collision. Only one boy likes the third girl, so there are no collisions with her and thus we have 4 collisions total.
Example Case 2. For each girl there is only one boy who likes her, so there are no collisions at all.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to make function, which returns the sum of a sequence of integers.

The sequence is defined by 3 non-negative values: **begin**, **end**, **step**.

If **begin** value is greater than the **end**, function should returns **0**

*Examples*

~~~if-not:nasm

~~~

This is the first kata in the series:

1) Sum of a sequence (this kata)  
2) [Sum of a Sequence [Hard-Core Version]](https://www.codewars.com/kata/sum-of-a-sequence-hard-core-version/javascript)

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