vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Polycarp likes numbers that are divisible by 3.

He has a huge number s. Polycarp wants to cut from it the maximum number of numbers that are divisible by 3. To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after m such cuts, there will be m+1 parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by 3.

For example, if the original number is s=3121, then Polycarp can cut it into three parts with two cuts: 3|1|21. As a result, he will get two numbers that are divisible by 3.

Polycarp can make an arbitrary number of vertical cuts, where each cut is made between a pair of adjacent digits. The resulting numbers cannot contain extra leading zeroes (that is, the number can begin with 0 if and only if this number is exactly one character '0'). For example, 007, 01 and 00099 are not valid numbers, but 90, 0 and 10001 are valid.

What is the maximum number of numbers divisible by 3 that Polycarp can obtain?

Input

The first line of the input contains a positive integer s. The number of digits of the number s is between 1 and 2⋅10^5, inclusive. The first (leftmost) digit is not equal to 0.

Output

Print the maximum number of numbers divisible by 3 that Polycarp can get by making vertical cuts in the given number s.

Examples

Input

3121


Output

2


Input

6


Output

1


Input

1000000000000000000000000000000000


Output

33


Input

201920181


Output

4

Note

In the first example, an example set of optimal cuts on the number is 3|1|21.

In the second example, you do not need to make any cuts. The specified number 6 forms one number that is divisible by 3.

In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit 1 and 33 digits 0. Each of the 33 digits 0 forms a number that is divisible by 3.

In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers 0, 9, 201 and 81 are divisible by 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are $n$ positive integers $a_1, a_2, \dots, a_n$. For the one move you can choose any even value $c$ and divide by two all elements that equal $c$.

For example, if $a=[6,8,12,6,3,12]$ and you choose $c=6$, and $a$ is transformed into $a=[3,8,12,3,3,12]$ after the move.

You need to find the minimal number of moves for transforming $a$ to an array of only odd integers (each element shouldn't be divisible by $2$).


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow.

The first line of a test case contains $n$ ($1 \le n \le 2\cdot10^5$) — the number of integers in the sequence $a$. The second line contains positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

The sum of $n$ for all test cases in the input doesn't exceed $2\cdot10^5$.


-----Output-----

For $t$ test cases print the answers in the order of test cases in the input. The answer for the test case is the minimal number of moves needed to make all numbers in the test case odd (i.e. not divisible by $2$).


-----Example-----
Input
4
6
40 6 40 3 20 1
1
1024
4
2 4 8 16
3
3 1 7

Output
4
10
4
0



-----Note-----

In the first test case of the example, the optimal sequence of moves can be as follows:

  before making moves $a=[40, 6, 40, 3, 20, 1]$;  choose $c=6$;  now $a=[40, 3, 40, 3, 20, 1]$;  choose $c=40$;  now $a=[20, 3, 20, 3, 20, 1]$;  choose $c=20$;  now $a=[10, 3, 10, 3, 10, 1]$;  choose $c=10$;  now $a=[5, 3, 5, 3, 5, 1]$ — all numbers are odd. 

Thus, all numbers became odd after $4$ moves. In $3$ or fewer moves, you cannot make them all odd.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tara was completing an Algorithms assignment and got stuck on a question. She thought of who can help her, and got reminded of Kabir who has good problem solving skills. The question is:
Given N$N$ the number of elements in the sequence A1$A_1$,A2$A_2$ … An$A_n$. Find out the prime factor which occurred maximum number of times among the largest prime factor corresponding to each element. if there are more than one such prime factors print the largest one.
You are friends with Kabir, help him to solve the problem for Tara.

-----Input:-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T test cases follows. 
- First line of each test case contains N$N$, the number of elements in the sequence.
- Second line contains N space separated elements A1$A_1$,A2$A_2$ … An$A_n$.

-----Output:-----
- For each test case, print a single line, the number which occurs maximum number of times from the largest prime factor corresponding to each element.

-----Constraints-----
- 1≤T≤10$1 \leq T \leq 10$
- 1≤N≤105$1 \leq N \leq 10^5$
- 2≤A[i]≤105$2 \leq A[i] \leq 10^5$

-----Sample Input:-----
1
7

3 2 15 6 8 5 10

-----Sample Output:-----
5

-----EXPLANATION:-----
The largest prime factors of numbers are:
3 2  5  3  2  5  5 , of which 5 is most frequent.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The girl Taylor has a beautiful calendar for the year y. In the calendar all days are given with their days of week: Monday, Tuesday, Wednesday, Thursday, Friday, Saturday and Sunday.

The calendar is so beautiful that she wants to know what is the next year after y when the calendar will be exactly the same. Help Taylor to find that year.

Note that leap years has 366 days. The year is leap if it is divisible by 400 or it is divisible by 4, but not by 100 (https://en.wikipedia.org/wiki/Leap_year).


-----Input-----

The only line contains integer y (1000 ≤ y < 100'000) — the year of the calendar.


-----Output-----

Print the only integer y' — the next year after y when the calendar will be the same. Note that you should find the first year after y with the same calendar.


-----Examples-----
Input
2016

Output
2044

Input
2000

Output
2028

Input
50501

Output
50507



-----Note-----

Today is Monday, the 13th of June, 2016.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S with repeated characters. The task is to rearrange characters in a string such that no two adjacent characters are the same.
Note: The string has only lowercase English alphabets and it can have multiple solutions. Return any one of them.
Example 1:
Input : str = "geeksforgeeks"
Output: 1
Explanation: All the repeated characters of the
given string can be rearranged so that no 
adjacent characters in the string is equal.
Any correct rearrangement will show a output
of 1.
Example 2:
Input : str = "bbbbb"
Output: 0
Explanation: Repeated characters in the string
cannot be rearranged such that there should not
be any adjacent repeated character.
Your task :
You don't have to read input or print anything. Your task is to complete the functionrearrangeString() which takes the string as input and returns the modified string. If the string cannot be modified return "-1".
Note:The generatedoutput is 1 if the string is successfully rearranged and is 0 if rearranging is not possible.
 
Expected Time Complexity : O(NlogN), N = length of String
Expected Auxiliary Space : O(number of english alphabets)
 
Constraints :
1 <= length of string <= 10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke is visiting a shop in Tokyo called 109 to buy some logs.
He wants n logs: one of length 1, one of length 2, ..., and one of length n.
The shop has n+1 logs in stock: one of length 1, one of length 2, \dots, and one of length n+1. Each of these logs is sold for 1 yen (the currency of Japan).
He can cut these logs as many times as he wants after buying them. That is, he can get k logs of length L_1, \dots, L_k from a log of length L, where L = L_1 + \dots + L_k. He can also throw away unwanted logs.
Snuke wants to spend as little money as possible to get the logs he wants.
Find the minimum amount of money needed to get n logs of length 1 to n.

-----Constraints-----
 - 1 \leq n \leq 10^{18}

-----Input-----
Input is given from Standard Input in the following format:
n

-----Output-----
Print the minimum amount of money needed to get n logs of length 1 to n.

-----Sample Input-----
4

-----Sample Output-----
3

One way to get the logs he wants with 3 yen is:
 - Buy logs of length 2, 4, and 5.
 - Cut the log of length 5 into two logs of length 1 each and a log of length 3.
 - Throw away one of the logs of length 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"



Note:
In the string, each word is separated by single space and there will not be any extra space in the string.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given n integer ranges, the task is to find the maximum occurring integer in these ranges. If more than one such integer exists, find the smallest one. The ranges are given as two arrays L[] and R[].  L[i] consists of starting point of range and R[i] consists of corresponding end point of the range. 
For example consider the following ranges.
L[] = {2, 1, 3}, R[] = {5, 3, 9)
Ranges represented by above arrays are.
[2, 5] = {2, 3, 4, 5}
[1, 3] = {1, 2, 3}
[3, 9] = {3, 4, 5, 6, 7, 8, 9}
The maximum occurred integer in these ranges is 3.
Example 1:
Input:
n = 4
L[] = {1,4,3,1}
R[] = {15,8,5,4}
Output: 4
Explanation: The given ranges are [1,15]
 [4, 8] [3, 5] [1, 4]. The number that 
is most common or appears most times in 
the ranges is 4.
Example 2:
Input:
n = 5
L[] = {1,5,9,13,21}
R[] = {15,8,12,20,30}
Output: 5
Explanation: The given ranges are 
[1,15] [5, 8] [9, 12] [13, 20] 
[21, 30]. The number that is most 
common or appears most times in 
the ranges is 5.
Your Task:
The task is to complete the function maxOccured() which returns the maximum occured integer in all ranges.
Expected Time Complexity: O(n+maxx).
Expected Auxiliary Space: O(maxx).
-maxx is maximum element in R[]
Constraints:
1 ≤ n ≤ 10^{6}
0 ≤ L[i], R[i] ≤ 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Greg wants to build a string, $\mbox{S}$ of length $N$. Starting with an empty string, he can perform $2$ operations:

Add a character to the end of $\mbox{S}$ for $\mbox{A}$ dollars.

Copy any substring of $\mbox{S}$, and then add it to the end of $\mbox{S}$ for $\mbox{B}$ dollars.

Calculate minimum amount of money Greg needs to build $\mbox{S}$.

Input Format

The first line contains number of testcases $\mathbf{T}$.        

The $2\times T$ subsequent lines each describe a test case over $2$ lines: 

The first contains $3$ space-separated integers, $N$, $\mbox{A}$ , and $\mbox{B}$, respectively. 

The second contains $\mbox{S}$ (the string Greg wishes to build).

Constraints

$1\leq T\leq3$
$1\leq N\leq3\times10^4$
$1\leq A,B\leq10000$
$\mbox{S}$ is composed of lowercase letters only.

Output Format

On a single line for each test case, print the minimum cost (as an integer) to build $\mbox{S}$.

Sample Input
2
9 4 5
aabaacaba
9 8 9
bacbacacb

Sample Output
26
42

Explanation

Test Case 0: 

$S_{initial}=$ ""; $S_{final}=$ "$aaba aaba$" 

Append "$a$"; $S=$ "$a$"; cost is $4$ 

Append "$a$"; $S=$ "$aa$"; cost is $4$ 

Append "$\boldsymbol{b}$"; $S=$ "$\textit{aab}$"; cost is $4$ 

Copy and append "$\boldsymbol{a}\boldsymbol{a}$"; $S=$ "$a abaa$"; cost is $5$ 

Append "$\textbf{C}$"; $S=$ "$a a b a c$"; cost is $4$ 

Copy and append "$\boldsymbol{aba}$"; $S=$ "$aaba aaba$"; cost is $5$        

Summing each cost, we get $4+4+4+5+4+5=26$, so our output for Test Case 1 is $26$.

Test Case 1: 

$S_{initial}=$ ""; $S_{final}=$ "$bacbacacb$" 

Append "$\boldsymbol{b}$"; $S=$ "$\boldsymbol{b}$"; cost is $8$ 

Append "$\boldsymbol{\alpha}$"; $S=$ "$\textbf{ba}$"; cost is $8$ 

Append "$\textbf{C}$"; $S=$ "$\textbf{bac}$"; cost is $8$ 

Copy and append "$\textbf{bac}$"; $S=$ "$bacbac$"; cost is $9$ 

Copy and append "$\boldsymbol{acb}$"; $S=$ "$bacbacacb$"; cost is $9$

Summing each cost, we get $8+8+8+9+9=42$, so our output for Test Case 2 is $\textbf{42}$.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
The Galaxy contains *n* planets, there are many different living creatures inhabiting each planet. And each creature can get into troubles! Space rescuers know it perfectly well and they are always ready to help anyone who really needs help. All you need to do is call for them. 

Now the space rescuers plan to build the largest in the history of the Galaxy rescue station; however, the rescue station's location is yet to be determined. As some cases are real emergencies, the rescuers want to find such a point in the Galaxy from which it would be possible to get to the remotest planet in the minimum possible time. In other words, the rescuers need such point in the space that the distance between it and the planet remotest from it was minimal (if we compare this point with all other possible points in the space). Unfortunately, the rescuers can't sole this problem.

As the planets are quite remote from each other, they can be considered as points in Euclidean three-dimensional space. The distance between points (*x**i*,<=*y**i*,<=*z**i*) and (*x**j*,<=*y**j*,<=*z**j*) can be calculated by the formula . The rescue station can be positioned in any point in the space. It can also coincide with some planet. 

Galaxy is in danger! Save the space rescuers and find the required point for them.

Input Specification:
The first line of the input file contains integer *n* — the number of planets (1<=≤<=*N*<=≤<=100). Each of the following *n* lines contains information about the planets. The *i*-th line contains three integers *x**i*,<=*y**i*,<=*z**i* — the coordinates of the *i*-th planet (<=-<=104<=≤<=*x**i*,<=*y**i*,<=*z**i*<=≤<=104, 1<=≤<=*i*<=≤<=*n*). No two planets coincide.

Output Specification:
Print on the first line of the output file three space-separated real numbers *x*0,<=*y*0,<=*z*0 — the coordinates for the future base. If there are several solutions, you are allowed to print any of them. The answer will be accepted if the distance from this point to the remotest planet will differ from the juries' variant in no more than 10<=-<=6 in absolute or relative value.

Demo Input:
['5\n5 0 0\n-5 0 0\n0 3 4\n4 -3 0\n2 2 -2\n']

Demo Output:
['0.000 0.000 0.000\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are parking at a parking lot. You can choose from the following two fee plans:
 - Plan 1: The fee will be A×T yen (the currency of Japan) when you park for T hours.
 - Plan 2: The fee will be B yen, regardless of the duration.
Find the minimum fee when you park for N hours.

-----Constraints-----
 - 1≤N≤20
 - 1≤A≤100
 - 1≤B≤2000
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
N A B

-----Output-----
When the minimum fee is x yen, print the value of x.

-----Sample Input-----
7 17 120

-----Sample Output-----
119

 - If you choose Plan 1, the fee will be 7×17=119 yen.
 - If you choose Plan 2, the fee will be 120 yen.
Thus, the minimum fee is 119 yen.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dee Siduous is a botanist who specializes in trees. A lot of her research has to do with the formation of tree rings, and what they say about the growing conditions over the tree’s lifetime. She has a certain theory and wants to run some simulations to see if it holds up to the evidence gathered in the field.

One thing that needs to be done is to determine the expected number of rings given the outline of a tree. Dee has decided to model a cross section of a tree on a two dimenional grid, with the interior of the tree represented by a closed polygon of grid squares. Given this set of squares, she assigns rings from the outer parts of the tree to the inner as follows: calling the non-tree grid squares “ring $0$”, each ring $n$ is made up of all those grid squares that have at least one ring $(n-1)$ square as a neighbor (where neighboring squares are those that share an edge).

An example of this is shown in the figure below.

 Figure D.1 

Most of Dee’s models have been drawn on graph paper, and she has come to you to write a program to do this automatically for her. This way she’ll use less paper and save some $\ldots $ well, you know.

-----Input-----
The input will start with a line containing two positive integers $n$ $m$ specifying the number of rows and columns in the tree grid, where $n, m \leq 100$. After this will be $n$ rows containing $m$ characters each. These characters will be either ‘T’ indicating a tree grid square, or ‘.’.



-----Output-----
Output a grid with the ring numbers. If the number of rings is less than 10, use two characters for each grid square; otherwise use three characters for each grid square. Right justify all ring numbers in the grid squares, and use ‘.’ to fill in the remaining characters.

If a row or column does not contain a ring number it should still be output, filled entirely with ‘.’s.

-----Examples-----
Sample Input:
6 6
.TT...
TTTT..
TTTTT.
TTTTT.
TTTTTT
..T...
Sample Output:
...1.1......
.1.2.2.1....
.1.2.3.2.1..
.1.2.3.2.1..
.1.1.2.1.1.1
.....1......

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shil likes to perform Crazy Operation on an array A1,A2,...AN.

Given an array A1,A2,...AN and permutation P1,P2, ..,PN, a Crazy Operation consists of two parts:  

Perform Operation Bi = Ai for every i in 1..N

Perform Operation Ai = BPi  for every i in 1..N. Here P is a permutation from 1 to N.

Shil asks you to print the resulting array A1, A2,...AN after doing  Crazy Operation on  it , T times.

Input format:
The first line of input consists of two integers N and T. The next line consists of N integers  A1, A2,...AN. The next line consists of permutation P1,P2,...PN.

Output format:
Print the resulting A1,A2,...AN after doing  Crazy operations on it T times.

Constraints:
1≤N≤10^5
1≤T≤10^18
1≤Ai≤10^9

SAMPLE INPUT
5 3
1 2 3 4 5
3 4 5 2 1

SAMPLE OUTPUT
1 4 3 2 5

Explanation

On doing Crazy Operation 1st time resulting array will be (3,4,5,2,1).
On doing second time , resulting array will be (5,2,1,4,3).
On doing third time, resulting array will be (1,4,3,2,5).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr[] of N elements, the task is to find the maximum sum of lengths of all non-overlapping subarrays with K as the maximum element in the subarray.
Example 1:
Input: N = 9, K = 4
arr[] = {2, 1, 4, 9, 2, 3, 8, 3, 4} 
Output: 5
Explanation: {2, 1, 4} => Length = 3
             {3, 4} => Length = 2
             So, 3 + 2 = 5 is the answer.
Example 2:
Input: N = 7, K = 4
arr[] = {1, 2, 3, 2, 3, 4, 1} 
Output:  7
Explanation: {1, 2, 3, 2, 3, 4, 1} 
             => Length = 7.
 
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function calculateMaxSumLength() that takes array arr, integer N, and integer K as parameters and returns the sum of the length of all such subarrays.
 
Expected Time Complexity: O(N). 
Expected Auxiliary Space: O(1).
 
Constraints:
1 ≤ N ≤ 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bertown is under siege! The attackers have blocked all the ways out and their cannon is bombarding the city. Fortunately, Berland intelligence managed to intercept the enemies' shooting plan. Let's introduce the Cartesian system of coordinates, the origin of which coincides with the cannon's position, the Ox axis is directed rightwards in the city's direction, the Oy axis is directed upwards (to the sky). The cannon will make n more shots. The cannon balls' initial speeds are the same in all the shots and are equal to V, so that every shot is characterized by only one number alphai which represents the angle at which the cannon fires. Due to the cannon's technical peculiarities this angle does not exceed 45 angles (π / 4). We disregard the cannon sizes and consider the firing made from the point (0, 0).

The balls fly according to the known physical laws of a body thrown towards the horizon at an angle: 

vx(t) = V·cos(alpha) vy(t) = V·sin(alpha) – g·t x(t) = V·cos(alpha)·t y(t) = V·sin(alpha)·t – g·t2 / 2

Think of the acceleration of gravity g as equal to 9.8.

Bertown defends m walls. The i-th wall is represented as a vertical segment (xi, 0) - (xi, yi). When a ball hits a wall, it gets stuck in it and doesn't fly on. If a ball doesn't hit any wall it falls on the ground (y = 0) and stops. If the ball exactly hits the point (xi, yi), it is considered stuck. 

Your task is to find for each ball the coordinates of the point where it will be located in the end.

Input

The first line contains integers n and V (1 ≤ n ≤ 104, 1 ≤ V ≤ 1000) which represent the number of shots and the initial speed of every ball. The second line contains n space-separated real numbers alphai (0 < alphai < π / 4) which represent the angles in radians at which the cannon will fire. The third line contains integer m (1 ≤ m ≤ 105) which represents the number of walls. Then follow m lines, each containing two real numbers xi and yi (1 ≤ xi ≤ 1000, 0 ≤ yi ≤ 1000) which represent the wall’s coordinates. All the real numbers have no more than 4 decimal digits. The walls may partially overlap or even coincide.

Output

Print n lines containing two real numbers each — calculate for every ball the coordinates of its landing point. Your answer should have the relative or absolute error less than 10 - 4.

Examples

Input

2 10
0.7853
0.3
3
5.0 5.0
4.0 2.4
6.0 1.9


Output

5.000000000 2.549499369
4.000000000 0.378324889


Input

2 10
0.7853
0.3
2
4.0 2.4
6.0 1.9


Output

10.204081436 0.000000000
4.000000000 0.378324889

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number N, your task is to complete the function which generates all n-bit grey code sequences, a grey code sequence is a sequence such that successive patterns in it differ by one bit.
Example 1:
Input:
N = 2
Output: 00 01 11 10
Explanation: All 2-bit gray codes are
00, 01, 11, 10 such that successive
patterns in it differ by one bit.
Example 2:
Input:
N = 1
Output: 0 1
 
Your Task:
Complete the function generateCode() which takes an integer as input parameter and retruns an array of all N bit grey code sequence such that successive patterns in it differ by one bit.
Expected Time Complexity: O(N * 2^{N})
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 16

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