vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Mr. Knight is a chief architect of the project to build a new art museum. One day, he was struggling to determine the design of the building. He believed that a brilliant art museum must have an artistic building, so he started to search for a good motif of his building. The art museum has one big theme: "nature and human beings." To reflect the theme, he decided to adopt a combination of a cylinder and a prism, which symbolize nature and human beings respectively (between these figures and the theme, there is a profound relationship that only he knows).

Shortly after his decision, he remembered that he has to tell an estimate of the cost required to build to the financial manager. He unwillingly calculated it, and he returned home after he finished his report. However, you, an able secretary of Mr. Knight, have found that one field is missing in his report: the length of the fence required to surround the building. Fortunately you are also a good programmer, so you have decided to write a program that calculates the length of the fence.

To be specific, the form of his building is union of a cylinder and a prism. You may consider the twodimensional projection of the form, i.e. the shape of the building is considered to be union of a circle C and a polygon P. The fence surrounds the outside of the building. The shape of the building may have a hole in it, and the fence is not needed inside the building. An example is shown in the figure below.

<image>



Input

The input contains one test case.

A test case has the following format:

R
N x1 y1 x2 y2 ... xn yn


R is an integer that indicates the radius of C (1 ≤ R ≤ 1000), whose center is located at the origin. N is the number of vertices of P, and (xi, yi) is the coordinate of the i-th vertex of P. N, xi and yi are all integers satisfying the following conditions: 3 ≤ N ≤ 100,|xi| ≤ 1000 and |yi| ≤ 1000.

You may assume that C and P have one or more intersections.

Output

Print the length of the fence required to surround the building. The output value should be in a decimal fraction may not contain an absolute error more than 10-4.

It is guaranteed that the answer does not change by more than 10-6 when R is changed by up to 10-9.

Example

Input

2
8 -1 2 1 2 1 -3 2 -3 2 3 -2 3 -2 -3 -1 -3


Output

22.6303

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This kata is part of the collection [Mary's Puzzle Books](https://www.codewars.com/collections/marys-puzzle-books).

Mary brought home a "spot the differences" book. The book is full of a bunch of problems, and each problem consists of two strings that are similar. However, in each string there are a few characters that are different. An example puzzle from her book is:
```
String 1: "abcdefg"
String 2: "abcqetg"
```
Notice how the "d" from String 1 has become a "q" in String 2, and "f" from String 1 has become a "t" in String 2.

It's your job to help Mary solve the puzzles. Write a program `spot_diff`/`Spot` that will compare the two strings and return a list with the positions where the two strings differ. In the example above, your program should return `[3, 5]` because String 1 is different from String 2 at positions 3 and 5.

NOTES:

```if-not:csharp
• If both strings are the same, return `[]`
```
```if:csharp
• If both strings are the same, return `new List()`
```

• Both strings will always be the same length

• Capitalization and punctuation matter

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have c_1 letters 'a', c_2 letters 'b', ..., c_{26} letters 'z'. You want to build a beautiful string of length n from them (obviously, you cannot use the i-th letter more than c_i times). Each c_i is greater than n/3.

A string is called beautiful if there are no palindromic contiguous substrings of odd length greater than 1 in it. For example, the string "abacaba" is not beautiful, it has several palindromic substrings of odd length greater than 1 (for example, "aca"). Another example: the string "abcaa" is beautiful.

Calculate the number of different strings you can build, and print the answer modulo 998244353.

Input

The first line contains one integer n (3 ≤ n ≤ 400).

The second line contains 26 integers c_1, c_2, ..., c_{26} (n/3 < c_i ≤ n).

Output

Print one integer — the number of strings you can build, taken modulo 998244353.

Examples

Input


4
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2


Output


422500


Input


3
2 2 2 2 2 2 3 3 3 2 2 2 2 2 2 3 3 3 2 2 3 2 2 3 2 2


Output


16900


Input


400
348 322 247 158 209 134 151 267 268 176 214 379 372 291 388 135 147 304 169 149 193 351 380 368 181 340


Output


287489790

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string S and you need to check whether S contains two non overlapping substrings "XY" and "YX" in any order or not.
Note : All letters of the String are Uppercased.
 
Example 1:
Input:
S = "XYYX"
Output:
YES
Explanation: 
From stated input string "XY"
substring(1,2) and "YX" substring(3,4)
can be easily separated without overlap.
So output is "YES".
Example 2:
Input:
S = "XYX"
Output:
NO
Explanation: 
"XY" and "YX" substrings are present.
But they overlap with each other.
So, Output is "NO".
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function overlapPresent() which takes a String S and returns the answer.
 
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= |S| <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Berland is going through tough times — the dirt price has dropped and that is a blow to the country's economy. Everybody knows that Berland is the top world dirt exporter!

The President of Berland was forced to leave only k of the currently existing n subway stations.

The subway stations are located on a straight line one after another, the trains consecutively visit the stations as they move. You can assume that the stations are on the Ox axis, the i-th station is at point with coordinate x_{i}. In such case the distance between stations i and j is calculated by a simple formula |x_{i} - x_{j}|.

Currently, the Ministry of Transport is choosing which stations to close and which ones to leave. Obviously, the residents of the capital won't be too enthusiastic about the innovation, so it was decided to show the best side to the people. The Ministry of Transport wants to choose such k stations that minimize the average commute time in the subway!

Assuming that the train speed is constant (it is a fixed value), the average commute time in the subway is calculated as the sum of pairwise distances between stations, divided by the number of pairs (that is $\frac{n \cdot(n - 1)}{2}$) and divided by the speed of the train.

Help the Minister of Transport to solve this difficult problem. Write a program that, given the location of the stations selects such k stations that the average commute time in the subway is minimized.


-----Input-----

The first line of the input contains integer n (3 ≤ n ≤ 3·10^5) — the number of the stations before the innovation. The second line contains the coordinates of the stations x_1, x_2, ..., x_{n} ( - 10^8 ≤ x_{i} ≤ 10^8). The third line contains integer k (2 ≤ k ≤ n - 1) — the number of stations after the innovation.

The station coordinates are distinct and not necessarily sorted.


-----Output-----

Print a sequence of k distinct integers t_1, t_2, ..., t_{k} (1 ≤ t_{j} ≤ n) — the numbers of the stations that should be left after the innovation in arbitrary order. Assume that the stations are numbered 1 through n in the order they are given in the input. The number of stations you print must have the minimum possible average commute time among all possible ways to choose k stations. If there are multiple such ways, you are allowed to print any of them.


-----Examples-----
Input
3
1 100 101
2

Output
2 3 


-----Note-----

In the sample testcase the optimal answer is to destroy the first station (with x = 1). The average commute time will be equal to 1 in this way.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A grid is a perfect starting point for many games (Chess, battleships, Candy Crush!).

Making a digital chessboard I think is an interesting way of visualising how loops can work together.

Your task is to write a function that takes two integers `rows` and `columns` and returns a chessboard pattern as a two dimensional array.

So `chessBoard(6,4)` should return an array like this:


    [
            ["O","X","O","X"],
            ["X","O","X","O"],
            ["O","X","O","X"],
            ["X","O","X","O"],
            ["O","X","O","X"],
            ["X","O","X","O"]
    ]

And `chessBoard(3,7)` should return this:


    [
        ["O","X","O","X","O","X","O"],
        ["X","O","X","O","X","O","X"],
        ["O","X","O","X","O","X","O"]
    ]

The white spaces should be represented by an: `'O'`

and the black an: `'X'`

The first row should always start with a white space `'O'`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nikhil got to know about what is a matrice. He made several patterns using 1-d and 2-d matrices. One of which was his favorite pattern. Your task is to right a code for his favorite pattern.

NOTE :- To understand his favorite pattern see the sample output

Input:-

First line of code takes number of test cases 'N' as its input. The following N lines take size 'S' of a sqaure matrice as its input.

Output:-

Print Nikhils favorite pattern and seperate two different test cases with an empty line.

Constraint:-

N ≤ 10

S ≤ 10

SAMPLE INPUT
1
3

SAMPLE OUTPUT
123
894
765

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Fox Ciel is playing a card game with her friend Fox Jiro. There are *n* piles of cards on the table. And there is a positive integer on each card.

The players take turns and Ciel takes the first turn. In Ciel's turn she takes a card from the top of any non-empty pile, and in Jiro's turn he takes a card from the bottom of any non-empty pile. Each player wants to maximize the total sum of the cards he took. The game ends when all piles become empty.

Suppose Ciel and Jiro play optimally, what is the score of the game?

Input Specification:
The first line contain an integer *n* (1<=≤<=*n*<=≤<=100). Each of the next *n* lines contains a description of the pile: the first integer in the line is *s**i* (1<=≤<=*s**i*<=≤<=100) — the number of cards in the *i*-th pile; then follow *s**i* positive integers *c*1, *c*2, ..., *c**k*, ..., *c**s**i* (1<=≤<=*c**k*<=≤<=1000) — the sequence of the numbers on the cards listed from top of the current pile to bottom of the pile.

Output Specification:
Print two integers: the sum of Ciel's cards and the sum of Jiro's cards if they play optimally.

Demo Input:
['2\n1 100\n2 1 10\n', '1\n9 2 8 6 5 9 4 7 1 3\n', '3\n3 1 3 2\n3 5 4 6\n2 8 7\n', '3\n3 1000 1000 1000\n6 1000 1000 1000 1000 1000 1000\n5 1000 1000 1000 1000 1000\n']

Demo Output:
['101 10\n', '30 15\n', '18 18\n', '7000 7000\n']

Note:
In the first example, Ciel will take the cards with number 100 and 1, Jiro will take the card with number 10.

In the second example, Ciel will take cards with numbers 2, 8, 6, 5, 9 and Jiro will take cards with numbers 4, 7, 1, 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a String. Reverse each word in it where the words are separated by dots.
Example 1:
Input:
S = "i.like.this.program.very.much"
Output: 
i.ekil.siht.margorp.yrev.hcum
Explanation: 
The words are reversed as
follows:"i" -> "i","like"->"ekil",
"this"->"siht","program" -> "margorp",
"very" -> "yrev","much" -> "hcum".
Example 2:
Input: 
S = "pqr.mno"
Output: 
rqp.onm
Explanation: 
The words are reversed as
follows:"pqr" -> "rqp" ,
"mno" -> "onm"
Your Task:
You don't need to read input or print anything. Your task is to complete the functionreverseWords()which takes the string S as input and returns the resultant string by reversing all the words separated by dots.
Expected Time Complexity:O(|S|).
Expected Auxiliary Space:O(|S|).
Constraints:
1<=|S|<=10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a grid with $H$ rows and $W$ columns. $H + W$ is even. We denote the cell at the $i$-th row from the top and the $j$-th column from the left by ($i, j$). In any cell ($i, j$), an integer between $1$ and $9$ is written if $i+j$ is even, and either '+' or '*' is written if $i+j$ is odd.

You can get a mathematical expression by moving right or down $H + W - 2$ times from ($1, 1$) to ($H, W$) and concatenating all the characters written in the cells you passed in order. Your task is to maximize the calculated value of the resulting mathematical expression by choosing an arbitrary path from ($1, 1$) to ($H, W$). If the maximum value is $10^{15}$ or less, print the value. Otherwise, print $-1$.



Input

The input consists of a single test case in the format below.


$H$ $W$
$a_{1,1}$ ... $a_{1,W}$
...
$a_{H,1}$ ... $a_{H,W}$


The first line consists of two $H$ integers and $W$ ($1 \leq H, W \leq 50$). It is guaranteed that $H + W$ is even. The following $H$ lines represent the characters on the grid. $a_{i,j}$ represents the character written in the cell ($i, j$). In any cell ($i, j$), an integer between $1$ and $9$ is written if $i+j$ is even, and either '+' or '*' is written if $i+1$ is odd.

Output

Print the answer in one line.

Examples

Input

3 3
1+2
+9*
1*5


Output

46


Input

1 31
9*9*9*9*9*9*9*9*9*9*9*9*9*9*9*9


Output

-1


Input

5 5
2+2+1
+1+1+
1+2+2
+1+1+
1+1+2


Output

10


Input

9 7
8+9*4*8
*5*2+3+
1*3*2*2
*5*1+9+
1+2*2*2
*3*6*2*
7*7+6*5
*5+7*2+
3+3*6+8


Output

86408

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:


Input Specification:
The input contains a single integer *a* (1<=≤<=*a*<=≤<=18257).

Output Specification:
Print a single integer *output* (1<=≤<=*output*<=≤<=2·109).

Demo Input:
['2\n']

Demo Output:
['13']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An undirected graph is called k-regular, if the degrees of all its vertices are equal k. An edge of a connected graph is called a bridge, if after removing it the graph is being split into two connected components.

Build a connected undirected k-regular graph containing at least one bridge, or else state that such graph doesn't exist.


-----Input-----

The single line of the input contains integer k (1 ≤ k ≤ 100) — the required degree of the vertices of the regular graph.


-----Output-----

Print "NO" (without quotes), if such graph doesn't exist. 

Otherwise, print "YES" in the first line and the description of any suitable graph in the next lines.

The description of the made graph must start with numbers n and m — the number of vertices and edges respectively. 

Each of the next m lines must contain two integers, a and b (1 ≤ a, b ≤ n, a ≠ b), that mean that there is an edge connecting the vertices a and b. A graph shouldn't contain multiple edges and edges that lead from a vertex to itself. A graph must be connected, the degrees of all vertices of the graph must be equal k. At least one edge of the graph must be a bridge. You can print the edges of the graph in any order. You can print the ends of each edge in any order.

The constructed graph must contain at most 10^6 vertices and 10^6 edges (it is guaranteed that if at least one graph that meets the requirements exists, then there also exists the graph with at most 10^6 vertices and at most 10^6 edges). 


-----Examples-----
Input
1

Output
YES
2 1
1 2



-----Note-----

In the sample from the statement there is a suitable graph consisting of two vertices, connected by a single edge.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Simple interest on a loan is calculated by simply taking the initial amount (the principal, p) and multiplying it by a rate of interest (r) and the number of time periods (n). 

Compound interest is calculated by adding the interest after each time period to the amount owed, then calculating the next interest payment based on the principal PLUS the interest from all previous periods.

Given a principal *p*, interest rate *r*, and a number of periods *n*, return an array [total owed under simple interest, total owed under compound interest]. 

```
EXAMPLES:

interest(100,0.1,1) = [110,110]
interest(100,0.1,2) = [120,121]
interest(100,0.1,10) = [200,259]
```
 
Round all answers to the nearest integer. Principal will always be an integer between 0 and 9999; interest rate will be a decimal between 0 and 1; number of time periods will be an integer between 0 and 49. 
 
---

More on [Simple interest, compound interest and continuous interest](https://betterexplained.com/articles/a-visual-guide-to-simple-compound-and-continuous-interest-rates/)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After a long day, Alice and Bob decided to play a little game. The game board consists of $n$ cells in a straight line, numbered from $1$ to $n$, where each cell contains a number $a_i$ between $1$ and $n$. Furthermore, no two cells contain the same number. 

A token is placed in one of the cells. They take alternating turns of moving the token around the board, with Alice moving first. The current player can move from cell $i$ to cell $j$ only if the following two conditions are satisfied:   the number in the new cell $j$ must be strictly larger than the number in the old cell $i$ (i.e. $a_j > a_i$), and  the distance that the token travels during this turn must be a multiple of the number in the old cell (i.e. $|i-j|\bmod a_i = 0$). 

Whoever is unable to make a move, loses. For each possible starting position, determine who wins if they both play optimally. It can be shown that the game is always finite, i.e. there always is a winning strategy for one of the players.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the number of numbers.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$). Furthermore, there are no pair of indices $i \neq j$ such that $a_i = a_j$.


-----Output-----

Print $s$ — a string of $n$ characters, where the $i$-th character represents the outcome of the game if the token is initially placed in the cell $i$. If Alice wins, then $s_i$ has to be equal to "A"; otherwise, $s_i$ has to be equal to "B". 


-----Examples-----
Input
8
3 6 5 4 2 7 1 8

Output
BAAAABAB

Input
15
3 11 2 5 10 9 7 13 15 8 4 12 6 1 14

Output
ABAAAABBBAABAAB



-----Note-----

In the first sample, if Bob puts the token on the number (not position):   $1$: Alice can move to any number. She can win by picking $7$, from which Bob has no move.  $2$: Alice can move to $3$ and $5$. Upon moving to $5$, Bob can win by moving to $8$. If she chooses $3$ instead, she wins, as Bob has only a move to $4$, from which Alice can move to $8$.  $3$: Alice can only move to $4$, after which Bob wins by moving to $8$.  $4$, $5$, or $6$: Alice wins by moving to $8$.  $7$, $8$: Alice has no move, and hence she loses immediately.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A magic number is a number formed by concatenation of numbers 1, 14 and 144. We can use each of these numbers any number of times. Therefore 14144, 141414 and 1411 are magic numbers but 1444, 514 and 414 are not.

You're given a number. Determine if it is a magic number or not.


-----Input-----

The first line of input contains an integer n, (1 ≤ n ≤ 10^9). This number doesn't contain leading zeros.


-----Output-----

Print "YES" if n is a magic number or print "NO" if it's not.


-----Examples-----
Input
114114

Output
YES

Input
1111

Output
YES

Input
441231

Output
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array A of size N, and Q queries to deal with. For each query, you are given an integer X, and you're supposed to find out if X is present in the array A or not.

Input:
The first line contains two integers, N and Q, denoting the size of array A and number of queries. The second line contains N space separated integers, denoting the array of elements Ai. The next Q lines contain a single integer X per line.

Output:
For each query, print YES if the X is in the array, otherwise print NO.

Constraints:
1 ≤ N, Q ≤ 10^5
1 ≤ Ai ≤ 10^9
1 ≤ X ≤ 10^9

SAMPLE INPUT
5 10
50 40 30 20 10
10
20
30
40
50
60
70
80
90
100

SAMPLE OUTPUT
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
About to leave the university to go home, you notice dark clouds packed in the distance. Since you’re travelling by bicycle, you’re not looking forward to getting wet in the rain. Maybe if you race home quickly you might avert the rain. But then you’d get wet from sweat…

Facing this dilemma, you decide to consider this problem properly with all data available. First you look up the rain radar image that shows you precisely the predicted intensity of rainfall in the upcoming hours. You know at what time you want to be home at the latest. Also, you came up with a good estimate of how much you sweat depending on your cycling speed. Now the question remains: what is the best strategy to get home as dry as possible?

The rain is given for each minute interval in millilitres, indicating how wet you get from cycling through this — note that you can cycle just a fraction of a whole minute interval at the start and end of your trip: then only that fraction of the rain during that interval affects you. Sweating makes you wet at a rate of $s = c \cdot v^2$ per minute where $v$ is your speed in $\mathrm{km}/\mathrm{h}$ and $c$ is a positive constant you have determined. You have to cover the distance to your home in a given time (you don’t want to wait forever for it to become dry), but otherwise you can choose your strategy of when to leave and how fast to cycle (and even change speeds) as you wish. What is the least wet you can get from the combination of rain and sweat?

-----Input-----
 - One line containing a single positive integer $T$ ($0 < T \le 10000$), the number of minutes from now you want to be home by at the latest.
 - Another line with two positive floating point numbers: $c$ ($0.01 \le c \le 10$), the constant determining your sweating, and $d$ ($1 \le d \le 50$), the distance from university to home in kilometres.
 - $T$ more lines, where each line contains an integer $r_ i$ ($0 \le r_ i \le 100$) the number of millilitres of rain during the $i$-th minute interval (zero-based).

-----Output-----
On a single line print a floating point number: the number of millilitres of rain and sweat you get wet from when optimally planning your cycle home. Your answer should be correct up to an absolute or relative precision of $10^{-6}$.

-----Examples-----
Sample Input:
5
0.1 2.0
0
0
0
0
0
Sample Output:
288

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