vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Weird Rounding

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarp is crazy about round numbers. He especially likes the numbers divisible by 10*k*.

In the given number of *n* Polycarp wants to remove the least number of digits to get a number that is divisible by 10*k*. For example, if *k*<==<=3, in the number 30020 it is enough to delete a single digit (2). In this case, the result is 3000 that is divisible by 103<==<=1000.

Write a program that prints the minimum number of digits to be deleted from the given integer number *n*, so that the result is divisible by 10*k*. The result should not start with the unnecessary leading zero (i.e., zero can start only the number 0, which is required to be written as exactly one digit).

It is guaranteed that the answer exists.

Input Specification:
The only line of the input contains two integer numbers *n* and *k* (0<=≤<=*n*<=≤<=2<=000<=000<=000, 1<=≤<=*k*<=≤<=9).

It is guaranteed that the answer exists. All numbers in the input are written in traditional notation of integers, that is, without any extra leading zeros.

Output Specification:
Print *w* — the required minimal number of digits to erase. After removing the appropriate *w* digits from the number *n*, the result should have a value that is divisible by 10*k*. The result can start with digit 0 in the single case (the result is zero and written by exactly the only digit 0).

Demo Input:
['30020 3\n', '100 9\n', '10203049 2\n']

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

Note:
In the example 2 you can remove two digits: 1 and any 0. The result is number 0 which is divisible by any number.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It’s Halloween, and you’ve organized a bonfire and dance for the neighborhood children. The $n$ children have gathered into a ring to dance around the fire. Each child is wearing one of two fun yet spooky costumes: orange pumpkin, or black bat. Since it’s dark outside, you can only see a few children at a time, as they pass behind the bonfire. The children are not standing evenly so the number of children you can see at each time differs. In particular, numbering the children $0, 1, \ldots , n-1$ clockwise around the dance circle, at any given time you can see child $i$ in the center of your view, as well as $l_ i$ children before child $i$ and $r_ i$ children after child $i$ around the circle (i.e., child $i-l_ i, \ldots , i-1, i, i+1, \ldots , i+r_ i$, where the indices are of course taken modulo $n$).

To help pass the time while the children dance, you wonder to yourself: suppose you only knew, for each child $i$, whether an even or odd number of the $l_ i+r_ i+1$ children centered at child $i$ is wearing the orange pumpkin costume. Would you be able to uniquely reconstruct what costume each child is wearing? Clearly this is possible when $l_ i=r_ i=0$. But what if $l_ i$ and $r_ i$ are not always zero? Maybe there are multiple possible solutions, or none at all? You decide to investigate, later in the evening once you’re back at your computer.

-----Input-----
The first line of the input consists of a single integer $n$, indicating that there are $n$ children in the ring $(1 \leq n \leq 200000)$. The following $n$ lines describe the children you can see at different times. The $i$th line (indexed starting from zero) contains three space-separated non-negative integers $l_ i$, $r_ i$, $x_ i$ ($l_ i+r_ i+1\leq n,0\leq x_ i\leq 1$): you can see $l_ i+r_ i+1$ children when child $i$ is in the center of view ($l_ i$ to the left and $r_ i$ to the right of child $i$). If $x_ i=0$ then an even number of them are wearing the orange pumpkin costume. If $x_ i=1$ then an odd number of them are wearing the orange pumpkin costume.

-----Output-----
Compute the number of ways of assigning a costume to each child, consistent with your observations. Since this number might be large, print the result modulo $10^9 + 7$. (If it’s impossible to find any costume assignment that matches all parity constraints, print 0).

-----Examples-----
Sample Input:
5
1 0 0
1 0 1
3 0 1
3 0 0
3 0 1
Sample Output:
0

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* boys and *m* girls studying in the class. They should stand in a line so that boys and girls alternated there as much as possible. Let's assume that positions in the line are indexed from left to right by numbers from 1 to *n*<=+<=*m*. Then the number of integers *i* (1<=≤<=*i*<=&lt;<=*n*<=+<=*m*) such that positions with indexes *i* and *i*<=+<=1 contain children of different genders (position *i* has a girl and position *i*<=+<=1 has a boy or vice versa) must be as large as possible. 

Help the children and tell them how to form the line.

Input Specification:
The single line of the input contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=100), separated by a space.

Output Specification:
Print a line of *n*<=+<=*m* characters. Print on the *i*-th position of the line character "B", if the *i*-th position of your arrangement should have a boy and "G", if it should have a girl. 

Of course, the number of characters "B" should equal *n* and the number of characters "G" should equal *m*. If there are multiple optimal solutions, print any of them.

Demo Input:
['3 3\n', '4 2\n']

Demo Output:
['GBGBGB\n', 'BGBGBB\n']

Note:
In the first sample another possible answer is BGBGBG. 

In the second sample answer BBGBGB is also optimal.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An artist begins with a roll of ribbon, one inch wide. She clips it into pieces of various integral lengths, then aligns them with the bottom of a frame, rising vertically in columns, to form a mountain scene. A mountain scene must be uneven; if all columns are the same height, it’s a plain scene, not a mountain scene! It is possible that she may not use all of the ribbon.

If our artist has $4$ inches of ribbon and a $2 \times 2$ inch frame, she could form these scenes:

She would not form these scenes, because they’re plains, not mountains!

Given the length of the ribbon and the width and height of the frame, all in inches, how many different mountain scenes can she create? Two scenes are different if the regions covered by ribbon are different. There’s no point in putting more than one piece of ribbon in any column.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The input will consist of a single line with three space-separated integers $n$, $w$ and $h$, where $n$ ($0 \le n \le 10000$) is the length of the ribbon in inches, $w$ ($1 \le w \le 100$) is the width and $h$ ($1 \le h \le 100$) is the height of the frame, both in inches.

-----Output-----
Output a single integer, indicating the total number of mountain scenes our artist could possibly make, modulo $10^9 + 7$.

-----Examples-----
Sample Input 1:
25 5 5
Sample Output 1:
7770

Sample Input 2:
15 5 5
Sample Output 2:
6050

Sample Input 3:
10 10 1
Sample Output 3:
1022

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array, Arr of N numbers, and another number target, find three integers in the array such that the sum is closest to the target. Return the sum of the three integers.
Note: If there are multiple solutions, print the maximum one.
Example 1:
Input:
N = 6, target = 2
A[] = {-7,9,8,3,1,1}
Output: 2
Explanation: There is one triplet with sum
2 in the array. Triplet elements are -7,8,
1 whose sum is 2.
Example 2:
Input:
N = 4, target = 13
A[] = {5,2,7,5}
Output: 14
Explanation: There is one triplet with sum
12 and other with sum 14 in the array.
Triplet elements are 5, 2, 5 and 2, 7, 5
respectively. Since abs(13-12) ==
abs(13-14) maximum triplet sum will be
preferred i.e 14.
Your Task:
Complete threeSumClosest() function and return the expected answer.
Expected Time Complexity: O(N*N).
Expected Auxiliary Space: O(1).
Constraints:
3 ≤ N ≤ 10^{3}
-10^{5} ≤ A[i] ≤ 10^{5}
1 ≤ target ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a sequence of $n$ integers, $p(1),p(2),...,p(n)$ where each element is distinct and satisfies $1\leq p(x)\leq n$. For each $\boldsymbol{x}$ where $1\leq x\leq n$, that is $\boldsymbol{x}$ increments from $\mbox{1}$ to $n$, find any integer $y$ such that $p(p(y))\equiv x$ and keep a history of the values of $y$ in a return array.

Example   

$p=[5,2,1,3,4]$    

Each value of $\boldsymbol{x}$ between $\mbox{1}$ and $5$, the length of the sequence, is analyzed as follows:

$x=1\equiv p[3],p[4]=3$, so $p[p[4]]=1$
$x=2\equiv p[2],p[2]=2$, so $p[p[2]]=2$
$x=3\equiv p[4],p[5]=4$, so $p[p[5]]=3$
$x=4\equiv p[5],p[1]=5$, so $p[p[1]]=4$
$x=5\equiv p[1],p[3]=1$, so $p[p[3]]=5$

The values for $y$ are $[4,2,5,1,3]$.  

Function Description  

Complete the permutationEquation function in the editor below.   

permutationEquation has the following parameter(s):  

int p[n]: an array of integers  

Returns   

int[n]: the values of $y$ for all $\boldsymbol{x}$ in the arithmetic sequence $\mbox{1}$ to $n$

Input Format

The first line contains an integer $n$, the number of elements in the sequence. 

The second line contains $n$ space-separated integers $p[i]$ where $1\leq i\leq n$.

Constraints

$1\leq n\leq50$
$1\leq p[i]\leq50$, where $1\leq i\leq n$.
Each element in the sequence is distinct.

Sample Input 0
3
2 3 1

Sample Output 0
2
3
1

Explanation 0

Given the values of $p(1)=2$, $p(2)=3$, and $p(3)=1$, we calculate and print the following values for each $\boldsymbol{x}$ from $\mbox{1}$ to $n$:

$x=1\equiv p(3)=p(p(2))=p(p(y))$, so we print the value of $y=2$ on a new line.
$x=2\equiv p(1)=p(p(3))=p(p(y))$, so we print the value of $y=3$ on a new line.
$x=3\equiv p(2)=p(p(1))=p(p(y))$, so we print the value of $y=1$ on a new line.

Sample Input 1
5
4 3 5 1 2

Sample Output 1
1
3
5
4
2

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
The sequence is called ordered if it is non-decreasing or non-increasing. For example, sequnces [3, 1, 1, 0] and [1, 2, 3, 100] are ordered, but the sequence [1, 3, 3, 1] is not. You are given a sequence of numbers. You are to find it's shortest subsequence which is not ordered.

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Input Specification:
The first line of the input contains one integer *n* (1<=≤<=*n*<=≤<=105). The second line contains *n* space-separated integers — the given sequence. All numbers in this sequence do not exceed 106 by absolute value.

Output Specification:
If the given sequence does not contain any unordered subsequences, output 0. Otherwise, output the length *k* of the shortest such subsequence. Then output *k* integers from the range [1..*n*] — indexes of the elements of this subsequence. If there are several solutions, output any of them.

Demo Input:
['5\n67 499 600 42 23\n', '3\n1 2 3\n', '3\n2 3 1\n']

Demo Output:
['3\n1 3 5\n', '0\n', '3\n1 2 3\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sereja has an array A of N positive integers : A[1], A[2], A[3], ... , A[N]. 

In a single operation on the array, he performs the following two steps :  

- Pick two indices i, j s.t. A[i] > A[j]
- A[i] -= A[j]

Sereja can apply these operations any number of times (possibly zero), such that the sum of resulting elements of the array is as small as possible.

Help Sereja find this minimum sum.

-----Input-----

First line of input contains an integer T - the number of test cases. T test cases follow.

First line of each test case contains the integer N. The next line contains N integers — A[1], A[2], A[3], ... , A[N].

-----Output-----
For each test case, output a single line with the answer.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- 1 ≤ A[i] ≤ 109

-----Example-----
Input:
2
1
1
3
2 4 6

Output:
1
6

-----Explanation-----
Example case 2. In this case, one possible way in which Sereja can perform the operations could be as follows. 

-  Pick i = 2, j = 1. A[2] -= A[1]. Now the resulting array would be [2, 2, 6].
-  Pick i = 3, j = 2. A[3] -= A[2]. Now the resulting array would be [2, 2, 4].
-  Pick i = 3, j = 2. A[3] -= A[2]. Now the resulting array would be [2, 2, 2]. 

As the resulting array is [2 2 2], so the sum is 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"Bless us and splash us , precious . Thats a meaty mouthful . " said Gollum on seeing 
Bilbo Baggins . Poor Bilbo Baggins is lost in the Misty Mountains and worst of all now he is 
stuck with Gollum who wants to finish him off. As Mr. Bilbo Baggins is clever , he convinced 
Gollum to play a game of riddles where if Bilbo answers correctly to the riddle given by Gollum ,
he wins and Gollum shows him the way out of the mountains . But if he loses , then Golumn would 
finish him off. Gollum gives Bilbo a fixed quantity of sand , say x units and also gives 
the quantity of sand required for each digit (1-9) , i.e he gives 9 numbers (x1,x2...x9) where xi 
represents sand required for ith digit . 
Now he ask Baggins to output the largest number possible using the given x units of sand.
Bilbo Baggins find this problem quite difficult and thus seeks your help .

Your task is simply to output the largest number possible which can be formed using x units of sand , given
sand required for each digit. If its impossible to form a number, print '-1'.
 

Input
First line contains integer T , the number of test cases. T testcases follow. The first line of each 
testcase contains integer n. Following n lines contain 9 integers , the amount of sand required for each number.  

Output
For each test case print largest number possible, if not possible to form the number , print  -1 .
 

Constraints
1 ≤ T ≤ 10
1 ≤n ≤ 10^6
1 ≤xi ≤ 10^5

SAMPLE INPUT
3
5
9 4 2 2 6 3 2 2 1
2
5 11 2 2 5 8 9 10 19
5
9 9 9 9 9 9 9 9 9

SAMPLE OUTPUT
99999
4
-1

Explanation

SAMPLE CASE 1 :
Maximum sand available is 5 units . So maximum number that can be formed using 5 units of sand is 99999 where each digit '9' consumed 1 unit of sand.

SAMPLE CASE 3 :
Maximum available sand is 5 units but sand required to form any of the 9 digits ( 1 to 9) is greater than maximum available sand which is 9 units . So its impossible to form any number and you have to print '-1' (without quotes).

NOTE : Ignore '0' digit . You have to form numbers without considering '0' digit.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You know that Japan is the country with almost the largest 'electronic devices per person' ratio. So you might be quite surprised to find out that the primary school in Japan teaches to count using a Soroban — an abacus developed in Japan. This phenomenon has its reasons, of course, but we are not going to speak about them. Let's have a look at the Soroban's construction.

Soroban consists of some number of rods, each rod contains five beads. We will assume that the rods are horizontal lines. One bead on each rod (the leftmost one) is divided from the others by a bar (the reckoning bar). This single bead is called go-dama and four others are ichi-damas. Each rod is responsible for representing a single digit from 0 to 9. We can obtain the value of a digit by following simple algorithm:
 -  Set the value of a digit equal to 0. -  If the go-dama is shifted to the right, add 5. -  Add the number of ichi-damas shifted to the left. 
Thus, the upper rod on the picture shows digit 0, the middle one shows digit 2 and the lower one shows 7. We will consider the top rod to represent the last decimal digit of a number, so the picture shows number 720.

Write the program that prints the way Soroban shows the given number *n*.

Input Specification:
The first line contains a single integer *n* (0<=≤<=*n*<=&lt;<=109).

Output Specification:
Print the description of the decimal digits of number *n* from the last one to the first one (as mentioned on the picture in the statement), one per line. Print the beads as large English letters 'O', rod pieces as character '-' and the reckoning bar as '|'. Print as many rods, as many digits are in the decimal representation of number *n* without leading zeroes. We can assume that number 0 has no leading zeroes.

Demo Input:
['2\n', '13\n', '720\n']

Demo Output:
['O-|OO-OO\n', 'O-|OOO-O\nO-|O-OOO\n', 'O-|-OOOO\nO-|OO-OO\n-O|OO-OO\n']

Note:
none

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
After Fox Ciel won an onsite round of a programming contest, she took a bus to return to her castle. The fee of the bus was 220 yen. She met Rabbit Hanako in the bus. They decided to play the following game because they got bored in the bus.
 -  Initially, there is a pile that contains *x* 100-yen coins and *y* 10-yen coins. -  They take turns alternatively. Ciel takes the first turn. -  In each turn, they must take exactly 220 yen from the pile. In Ciel's turn, if there are multiple ways to take 220 yen, she will choose the way that contains the maximal number of 100-yen coins. In Hanako's turn, if there are multiple ways to take 220 yen, she will choose the way that contains the maximal number of 10-yen coins. -  If Ciel or Hanako can't take exactly 220 yen from the pile, she loses. 
 

Determine the winner of the game.

Input Specification:
The first line contains two integers *x* (0<=≤<=*x*<=≤<=106) and *y* (0<=≤<=*y*<=≤<=106), separated by a single space.

Output Specification:
If Ciel wins, print "Ciel". Otherwise, print "Hanako".

Demo Input:
['2 2\n', '3 22\n']

Demo Output:
['Ciel\n', 'Hanako\n']

Note:
In the first turn (Ciel's turn), she will choose 2 100-yen coins and 2 10-yen coins. In the second turn (Hanako's turn), she will choose 1 100-yen coin and 12 10-yen coins. In the third turn (Ciel's turn), she can't pay exactly 220 yen, so Ciel will lose.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
See the following triangle:
```
____________________________________
 1                                      
 2   4   2                              
 3   6   9   6   3                      
 4   8   12  16  12  8   4             
 5   10  15  20  25  20  15  10  5   
 ___________________________________
 
```
The total sum of the numbers in the triangle, up to the 5th line included, is ```225```, part of it, ```144```, corresponds to the total sum of the even terms and ```81``` to the total sum of the odd terms.

Create a function that may output an array with three results for each value of n.
```python
triang_mult(n)  ----> [total_sum, total_even_sum, total_odd_sum]
```
Our example will be:
```python
triang_mult(5) ----> [225, 144, 81]
```

Features of the random tests:
```
number of tests = 100
49 < n < 5000
```
Enjoy it!
This kata will be translated in another languages soon

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You may have heard of the pie rule before. It states that if two people wish to fairly share a slice of pie, one person should cut the slice in half, and the other person should choose who gets which slice. Alice and Bob have many slices of pie, and rather than cutting the slices in half, each individual slice will be eaten by just one person.

The way Alice and Bob decide who eats each slice is as follows. First, the order in which the pies are to be handed out is decided. There is a special token called the "decider" token, initially held by Bob. Until all the pie is handed out, whoever has the decider token will give the next slice of pie to one of the participants, and the decider token to the other participant. They continue until no slices of pie are left.

All of the slices are of excellent quality, so each participant obviously wants to maximize the total amount of pie they get to eat. Assuming both players make their decisions optimally, how much pie will each participant receive?

Input Specification:
Input will begin with an integer *N* (1<=≤<=*N*<=≤<=50), the number of slices of pie. 

Following this is a line with *N* integers indicating the sizes of the slices (each between 1 and 100000, inclusive), in the order in which they must be handed out.

Output Specification:
Print two integers. First, the sum of the sizes of slices eaten by Alice, then the sum of the sizes of the slices eaten by Bob, assuming both players make their decisions optimally.

Demo Input:
['3\n141 592 653\n', '5\n10 21 10 21 10\n']

Demo Output:
['653 733\n', '31 41\n']

Note:
In the first example, Bob takes the size 141 slice for himself and gives the decider token to Alice. Then Alice gives the size 592 slice to Bob and keeps the decider token for herself, so that she can then give the size 653 slice to herself.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Pasha has many hamsters and he makes them work out. Today, n hamsters (n is even) came to work out. The hamsters lined up and each hamster either sat down or stood up.

For another exercise, Pasha needs exactly <image> hamsters to stand up and the other hamsters to sit down. In one minute, Pasha can make some hamster ether sit down or stand up. How many minutes will he need to get what he wants if he acts optimally well?

Input

The first line contains integer n (2 ≤ n ≤ 200; n is even). The next line contains n characters without spaces. These characters describe the hamsters' position: the i-th character equals 'X', if the i-th hamster in the row is standing, and 'x', if he is sitting.

Output

In the first line, print a single integer — the minimum required number of minutes. In the second line, print a string that describes the hamsters' position after Pasha makes the required changes. If there are multiple optimal positions, print any of them.

Examples

Input

4
xxXx


Output

1
XxXx


Input

2
XX


Output

1
xX


Input

6
xXXxXx


Output

0
xXXxXx

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