vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A pair of two very large positive integers is given. Find their sum.
 
Example 1:
Input: s1 = "63457", s2 = "645"
Output: 64102
Explanation: 63457 + 645 = 64102
Example 2:
Input: s1 = "101", s2 = "102"
Output: 203
Explanation: 101 + 102 = 203
 
Your Task:
You don't need to read or print anything. Your task to complete the function add() which takes two numbers in string format as input parameter and returns their sum in string format.
 
Expected Time Complexity: O(max(len(s1), len(s2))
Expected Space Complexity: O(1)
 
Constraints:
1 <= |s1|, |s2| <= 100000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mark loves eating chocolates and also likes to be fit. Given the calorie count for every chocolate he eats, find what he has to do to burn the calories. 
The name of the chocolates along with its calorie count are given as follows:
Calories per one whole bar:
Dairy milk (D)
238
Twix (T)
244
Milky Bar (M)
138
Bounty (B)
279
Crunchie (C)
186
The exercises preferred by him and the calories burnt are as follows:
Calories burnt per km:
Running
50
Cycling
5
Walking
0.5
Find the number of kilometers he has to run, cycle or walk to burn all of the calories. 
Priority given to the exercises is as follows: 
Running > Cycling > Walking

-----Input:-----
- It is a one line string consisting of the names(initial letter) of all the chocolates he has eaten.

-----Output:-----
Print three lines. First line representing how much he ran(in km), second line representing how much he cycled(in km), third line representing how much he walked(in km).

-----Constraints-----
- 1 <= length of input string <= 10. 

-----Sample Input:-----
DDTM

-----Sample Output:-----
17
1
6

-----EXPLANATION:-----
Calorie intake = 238 + 238 + 244 + 138 = 858
( 17km x 50 ) + ( 1km x 5 ) + ( 6km x 0.5 ) = 858.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice and Bob begin their day with a quick game. They first choose a starting number X_0 ≥ 3 and try to reach one million by the process described below. 

Alice goes first and then they take alternating turns. In the i-th turn, the player whose turn it is selects a prime number smaller than the current number, and announces the smallest multiple of this prime number that is not smaller than the current number.

Formally, he or she selects a prime p < X_{i} - 1 and then finds the minimum X_{i} ≥ X_{i} - 1 such that p divides X_{i}. Note that if the selected prime p already divides X_{i} - 1, then the number does not change.

Eve has witnessed the state of the game after two turns. Given X_2, help her determine what is the smallest possible starting number X_0. Note that the players don't necessarily play optimally. You should consider all possible game evolutions.


-----Input-----

The input contains a single integer X_2 (4 ≤ X_2 ≤ 10^6). It is guaranteed that the integer X_2 is composite, that is, is not prime.


-----Output-----

Output a single integer — the minimum possible X_0.


-----Examples-----
Input
14

Output
6

Input
20

Output
15

Input
8192

Output
8191



-----Note-----

In the first test, the smallest possible starting number is X_0 = 6. One possible course of the game is as follows:   Alice picks prime 5 and announces X_1 = 10  Bob picks prime 7 and announces X_2 = 14. 

In the second case, let X_0 = 15.   Alice picks prime 2 and announces X_1 = 16  Bob picks prime 5 and announces X_2 = 20.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Dima misbehaved during a math lesson a lot and the nasty teacher Mr. Pickles gave him the following problem as a punishment. 

Find all integer solutions x (0 < x < 10^9) of the equation:x = b·s(x)^{a} + c,  

where a, b, c are some predetermined constant values and function s(x) determines the sum of all digits in the decimal representation of number x.

The teacher gives this problem to Dima for each lesson. He changes only the parameters of the equation: a, b, c. Dima got sick of getting bad marks and he asks you to help him solve this challenging problem.


-----Input-----

The first line contains three space-separated integers: a, b, c (1 ≤ a ≤ 5; 1 ≤ b ≤ 10000;  - 10000 ≤ c ≤ 10000).


-----Output-----

Print integer n — the number of the solutions that you've found. Next print n integers in the increasing order — the solutions of the given equation. Print only integer solutions that are larger than zero and strictly less than 10^9.


-----Examples-----
Input
3 2 8

Output
3
10 2008 13726 
Input
1 2 -18

Output
0

Input
2 2 -1

Output
4
1 31 337 967

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Little Pony and Sort by Shift

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day, Twilight Sparkle is interested in how to sort a sequence of integers *a*1,<=*a*2,<=...,<=*a**n* in non-decreasing order. Being a young unicorn, the only operation she can perform is a unit shift. That is, she can move the last element of the sequence to its beginning:

Help Twilight Sparkle to calculate: what is the minimum number of operations that she needs to sort the sequence?

Input Specification:
The first line contains an integer *n* (2<=≤<=*n*<=≤<=105). The second line contains *n* integer numbers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=105).

Output Specification:
If it's impossible to sort the sequence output -1. Otherwise output the minimum number of operations Twilight Sparkle needs to sort it.

Demo Input:
['2\n2 1\n', '3\n1 3 2\n', '2\n1 2\n']

Demo Output:
['1\n', '-1\n', '0\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Capitalization is writing a word with its first letter as a capital letter. Your task is to capitalize the given word.

Note, that during capitalization all the letters except the first one remains unchanged.

Input Specification:
A single line contains a non-empty word. This word consists of lowercase and uppercase English letters. The length of the word will not exceed 103.

Output Specification:
Output the given word after capitalization.

Demo Input:
['ApPLe\n', 'konjac\n']

Demo Output:
['ApPLe\n', 'Konjac\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Anfisa the monkey got disappointed in word processors as they aren't good enough at reflecting all the range of her emotions, that's why she decided to switch to graphics editors. Having opened the BerPaint, she saw a white rectangle W × H in size which can be painted on. First Anfisa learnt to navigate the drawing tool which is used to paint segments and quickly painted on that rectangle a certain number of black-colored segments. The resulting picture didn't seem bright enough to Anfisa, that's why she turned her attention to the "fill" tool which is used to find a point on the rectangle to paint and choose a color, after which all the area which is the same color as the point it contains, is completely painted the chosen color. Having applied the fill several times, Anfisa expressed her emotions completely and stopped painting. Your task is by the information on the painted segments and applied fills to find out for every color the total area of the areas painted this color after all the fills.

Input

The first input line has two integers W and H (3 ≤ W, H ≤ 104) — the sizes of the initially white rectangular painting area. The second line contains integer n — the number of black segments (0 ≤ n ≤ 100). On the next n lines are described the segments themselves, each of which is given by coordinates of their endpoints x1, y1, x2, y2 (0 < x1, x2 < W, 0 < y1, y2 < H). All segments have non-zero length. The next line contains preset number of fills m (0 ≤ m ≤ 100). Each of the following m lines defines the fill operation in the form of "x y color", where (x, y) are the coordinates of the chosen point (0 < x < W, 0 < y < H), and color — a line of lowercase Latin letters from 1 to 15 symbols in length, determining the color. All coordinates given in the input are integers. Initially the rectangle is "white" in color, whereas the segments are drawn "black" in color.

Output

For every color present in the final picture print on the single line the name of the color and the total area of areas painted that color with an accuracy of 10 - 6. Print the colors in any order. 

Examples

Input

4 5
6
1 1 1 3
1 3 3 3
3 3 3 1
3 1 1 1
1 3 3 1
1 1 3 3
2
2 1 red
2 2 blue


Output

blue 0.00000000
white 20.00000000


Input

5 5
5
1 1 2 2
2 2 4 2
4 2 4 4
4 4 2 4
2 4 2 2
2
3 3 black
3 3 green


Output

green 4.00000000
white 21.00000000


Input

7 4
9
1 2 2 3
2 3 3 2
3 2 2 1
2 1 1 2
3 2 4 2
4 2 5 3
5 3 6 2
6 2 5 1
5 1 4 2
2
2 2 black
2 2 red


Output

red 2.00000000
white 26.00000000

Note

Initially the black segments painted by Anfisa can also be painted a color if any of the chosen points lays on the segment. The segments have areas equal to 0. That is why if in the final picture only parts of segments is painted some color, then the area, painted the color is equal to 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Krabs loves money. He enters a bank and sees that there are n rooms arranged in a row. The only rooms with doors are the two rooms on either corner. Initially, all the rooms are locked (including the corner ones). To enter a room, it must be unlocked with a key.
Mr. Krabs is able to steal k keys from the sleeping night guard. Each key can be used to unlock only one room. To reach one of the inner rooms, he has to unlock an adjacent room first.
Eg: If there are 5 rooms labelled: 1 2 3 4 5
Only Rooms 1 and 5 can be accessed initially. To unlock room 2, either room 1 or room 3 must be unlocked. Similarly to unlock Room 4, he must unlock room 5 or room 3 first.
Each room has some money in it. The money present in room i is given by A[i]. Using the k keys, calculate what is the maximum possible amount of money obtainable.

-----Input:-----
- First line will contain n,  number of rooms.
- Second line will contain space separated integers, denoting A[i], money present in each room.
- Third line will contain an integer, k, the number of keys available.

-----Output:-----
Maximum money obtained.

-----Constraints-----
- 1 <= Number of Rooms <= 10^5
- 1 <= A[i] <= 10^4
- 1 <= k <= Number of Rooms

-----Subtasks-----
- 40 points : 1 <= Number of Rooms <= 100
- 60 points : Number of Rooms > 100

-----Sample Input:-----
7
1 2 3 4 5 6 1
3

-----Sample Output:-----
12

-----Explanation:-----
For the first step, Mr. Krabs can only unlock the room at the left corner or the right corner. If he unlocks the room in the right corner, he obtains 1 dollar. He can then go on to unlock the second last room and gain 6 dollars, for a total of 7 dollars. Finally he can unlock the third last room and get 5 dollars, for a total of 12 dollars. 
This is the maximum amount of money he can get with only 3 keys.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Have you ever tried to explain to the coordinator, why it is eight hours to the contest and not a single problem has been prepared yet? Misha had. And this time he has a really strong excuse: he faced a space-time paradox! Space and time replaced each other.

The entire universe turned into an enormous clock face with three hands — hour, minute, and second. Time froze, and clocks now show the time h hours, m minutes, s seconds.

Last time Misha talked with the coordinator at t_1 o'clock, so now he stands on the number t_1 on the clock face. The contest should be ready by t_2 o'clock. In the terms of paradox it means that Misha has to go to number t_2 somehow. Note that he doesn't have to move forward only: in these circumstances time has no direction.

Clock hands are very long, and Misha cannot get round them. He also cannot step over as it leads to the collapse of space-time. That is, if hour clock points 12 and Misha stands at 11 then he cannot move to 1 along the top arc. He has to follow all the way round the clock center (of course, if there are no other hands on his way).

Given the hands' positions, t_1, and t_2, find if Misha can prepare the contest on time (or should we say on space?). That is, find if he can move from t_1 to t_2 by the clock face.


-----Input-----

Five integers h, m, s, t_1, t_2 (1 ≤ h ≤ 12, 0 ≤ m, s ≤ 59, 1 ≤ t_1, t_2 ≤ 12, t_1 ≠ t_2).

Misha's position and the target time do not coincide with the position of any hand.


-----Output-----

Print "YES" (quotes for clarity), if Misha can prepare the contest on time, and "NO" otherwise.

You can print each character either upper- or lowercase ("YeS" and "yes" are valid when the answer is "YES").


-----Examples-----
Input
12 30 45 3 11

Output
NO

Input
12 0 1 12 1

Output
YES

Input
3 47 0 4 9

Output
YES



-----Note-----

The three examples are shown on the pictures below from left to right. The starting position of Misha is shown with green, the ending position is shown with pink. Note that the positions of the hands on the pictures are not exact, but are close to the exact and the answer is the same. $\oplus 0 \theta$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this problem, we will deal with binary strings. Each character of a binary string is either a 0 or a 1. We will also deal with substrings; recall that a substring is a contiguous subsequence of a string. We denote the substring of string s starting from the l-th character and ending with the r-th character as s[l ... r]. The characters of each string are numbered from 1.

We can perform several operations on the strings we consider. Each operation is to choose a substring of our string and replace it with another string. There are two possible types of operations: replace 011 with 110, or replace 110 with 011. For example, if we apply exactly one operation to the string 110011110, it can be transformed into 011011110, 110110110, or 110011011.

Binary string a is considered reachable from binary string b if there exists a sequence s_1, s_2, ..., s_k such that s_1 = a, s_k = b, and for every i ∈ [1, k - 1], s_i can be transformed into s_{i + 1} using exactly one operation. Note that k can be equal to 1, i. e., every string is reachable from itself.

You are given a string t and q queries to it. Each query consists of three integers l_1, l_2 and len. To answer each query, you have to determine whether t[l_1 ... l_1 + len - 1] is reachable from t[l_2 ... l_2 + len - 1].

Input

The first line contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of string t.

The second line contains one string t (|t| = n). Each character of t is either 0 or 1.

The third line contains one integer q (1 ≤ q ≤ 2 ⋅ 10^5) — the number of queries.

Then q lines follow, each line represents a query. The i-th line contains three integers l_1, l_2 and len (1 ≤ l_1, l_2 ≤ |t|, 1 ≤ len ≤ |t| - max(l_1, l_2) + 1) for the i-th query.

Output

For each query, print either YES if t[l_1 ... l_1 + len - 1] is reachable from t[l_2 ... l_2 + len - 1], or NO otherwise. You may print each letter in any register.

Example

Input


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


Output


Yes
Yes
No

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
As you may know, MemSQL has American offices in both San Francisco and Seattle. Being a manager in the company, you travel a lot between the two cities, always by plane.

You prefer flying from Seattle to San Francisco than in the other direction, because it's warmer in San Francisco. You are so busy that you don't remember the number of flights you have made in either direction. However, for each of the last *n* days you know whether you were in San Francisco office or in Seattle office. You always fly at nights, so you never were at both offices on the same day. Given this information, determine if you flew more times from Seattle to San Francisco during the last *n* days, or not.

Input Specification:
The first line of input contains single integer *n* (2<=≤<=*n*<=≤<=100) — the number of days.

The second line contains a string of length *n* consisting of only capital 'S' and 'F' letters. If the *i*-th letter is 'S', then you were in Seattle office on that day. Otherwise you were in San Francisco. The days are given in chronological order, i.e. today is the last day in this sequence.

Output Specification:
Print "YES" if you flew more times from Seattle to San Francisco, and "NO" otherwise.

You can print each letter in any case (upper or lower).

Demo Input:
['4\nFSSF\n', '2\nSF\n', '10\nFFFFFFFFFF\n', '10\nSSFFSFFSFF\n']

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

Note:
In the first example you were initially at San Francisco, then flew to Seattle, were there for two days and returned to San Francisco. You made one flight in each direction, so the answer is "NO".

In the second example you just flew from Seattle to San Francisco, so the answer is "YES".

In the third example you stayed the whole period in San Francisco, so the answer is "NO".

In the fourth example if you replace 'S' with ones, and 'F' with zeros, you'll get the first few digits of π in binary representation. Not very useful information though.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You might have remembered Theatre square from the problem 1A. Now it's finally getting repaved.

The square still has a rectangular shape of $n \times m$ meters. However, the picture is about to get more complicated now. Let $a_{i,j}$ be the $j$-th square in the $i$-th row of the pavement.

You are given the picture of the squares:  if $a_{i,j} = $ "*", then the $j$-th square in the $i$-th row should be black;  if $a_{i,j} = $ ".", then the $j$-th square in the $i$-th row should be white. 

The black squares are paved already. You have to pave the white squares. There are two options for pavement tiles:  $1 \times 1$ tiles — each tile costs $x$ burles and covers exactly $1$ square;  $1 \times 2$ tiles — each tile costs $y$ burles and covers exactly $2$ adjacent squares of the same row. Note that you are not allowed to rotate these tiles or cut them into $1 \times 1$ tiles. 

You should cover all the white squares, no two tiles should overlap and no black squares should be covered by tiles.

What is the smallest total price of the tiles needed to cover all the white squares?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 500$) — the number of testcases. Then the description of $t$ testcases follow.

The first line of each testcase contains four integers $n$, $m$, $x$ and $y$ ($1 \le n \le 100$; $1 \le m \le 1000$; $1 \le x, y \le 1000$) — the size of the Theatre square, the price of the $1 \times 1$ tile and the price of the $1 \times 2$ tile.

Each of the next $n$ lines contains $m$ characters. The $j$-th character in the $i$-th line is $a_{i,j}$. If $a_{i,j} = $ "*", then the $j$-th square in the $i$-th row should be black, and if $a_{i,j} = $ ".", then the $j$-th square in the $i$-th row should be white.

It's guaranteed that the sum of $n \times m$ over all testcases doesn't exceed $10^5$.


-----Output-----

For each testcase print a single integer — the smallest total price of the tiles needed to cover all the white squares in burles.


-----Example-----
Input
4
1 1 10 1
.
1 2 10 1
..
2 1 10 1
.
.
3 3 3 7
..*
*..
.*.

Output
10
1
20
18



-----Note-----

In the first testcase you are required to use a single $1 \times 1$ tile, even though $1 \times 2$ tile is cheaper. So the total price is $10$ burles.

In the second testcase you can either use two $1 \times 1$ tiles and spend $20$ burles or use a single $1 \times 2$ tile and spend $1$ burle. The second option is cheaper, thus the answer is $1$.

The third testcase shows that you can't rotate $1 \times 2$ tiles. You still have to use two $1 \times 1$ tiles for the total price of $20$.

In the fourth testcase the cheapest way is to use $1 \times 1$ tiles everywhere. The total cost is $6 \cdot 3 = 18$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In order to pass time during your vacation, you decided to go on a hike to visit a scenic lake up in the mountains. Hiking to the lake will take you a full day, then you will stay there for a day to rest and enjoy the scenery, and then spend another day hiking home, for a total of three days. However, the accursed weather this summer is ridiculously warm and sunny, and since severe dehydration is not at the top of your priority list you want to schedule the three-day trip during some days where the two hiking days are the least warm. In particular you want to minimize the maximum temperature during the two hiking days. 

Given the current forecast of daily maximum temperatures during your vacation, what are the best days for your trip?

-----Input-----
The first line of input contains an integer $n$ ($3 \le n \le 50$), the length of your vacation in days. Then follows a line containing $n$ integers $t_1, t_2, \ldots , t_ n$ ($-20 \le t_ i \le 40$), where $t_ i$ is the temperature forecast for the $i$’th day of your vacation.

-----Output-----
Output two integers $d$ and $t$, where $d$ is the best day to start your trip, and $t$ is the resulting maximum temperature during the two hiking days. If there are many choices of $d$ that minimize the value of $t$, then output the smallest such $d$.

-----Examples-----
Sample Input:
5
23 27 31 28 30
Sample Output:
2 28

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Little Elephant from the Zoo of Lviv currently is on the military mission. There are N enemy buildings placed in a row and numbered from left to right strating from 0. Each building i (except the first and the last) has exactly two adjacent buildings with indices i-1 and i+1. The first and the last buildings have just a single adjacent building.

Some of the buildings contain bombs. When bomb explodes in some building it destroys it and all adjacent to it buildings.

You are given the string S of length N, where Si is 1 if the i-th building contains bomb, 0 otherwise. Find for the Little Elephant the number of buildings that will not be destroyed after all bombs explode. Please note that all bombs explode simultaneously.

-----Input-----
The first line contains single integer T - the number of test cases. T test cases follow. The first line of each test case contains the single integer N - the number of buildings. The next line contains the string S of length N consisted only of digits 0 and 1.

-----Output-----
In T lines print T inetgers - the answers for the corresponding test cases.

-----Constraints-----

1 <= T <= 100

1 <= N <= 1000

-----Example-----
Input:
3
3
010
5
10001
7
0000000

Output:
0
1
7

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