vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Alice and Bob want to play a game. They have n colored paper strips; the i-th strip is divided into a_i cells numbered from 1 to a_i. Each cell can have one of 3 colors.

In the beginning of the game, Alice and Bob put n chips, the i-th chip is put in the a_i-th cell of the i-th strip. Then they take turns, Alice is first. Each player during their turn has to choose one chip and move it 1, 2 or 3 cells backwards (i. e. if the current cell is x, then the chip can be moved to the cell x - 1, x - 2 or x - 3). There are two restrictions: the chip cannot leave the borders of the strip (for example, if the current cell is 3, then you can't move the chip 3 cells backwards); and some moves may be prohibited because of color of the current cell (a matrix f with size 3 × 3 is given, where f_{i, j} = 1 if it is possible to move the chip j cells backwards from the cell which has color i, or f_{i, j} = 0 if such move is prohibited). The player who cannot make a move loses the game.

Initially some cells may be uncolored. Bob can color all uncolored cells as he wants (but he cannot leave any cell uncolored). Let's call a coloring good if Bob can win the game no matter how Alice acts, if the cells are colored according to this coloring. Two colorings are different if at least one cell is colored in different colors in these two colorings.

Bob wants you to calculate the number of good colorings. Can you do it for him?

Since the answer can be really large, you have to print it modulo 998244353.

Input

The first line contains one integer n — the number of paper strips (1 ≤ n ≤ 1000).

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9), where a_i is the number of cells in the i-th strip.

The third line contains one integer m (1 ≤ m ≤ 1000) — the number of cells that are already colored.

Then m lines follow, each describing an already colored cell. The i-th of these lines contains three integers x_i, y_i and c_i (1 ≤ x_i ≤ n, 1 ≤ y_i ≤ a_{x_i}, 1 ≤ c_i ≤ 3) denoting that the cell y_i in the strip x_i has color c_i. It is guaranteed that if i ≠ j, then either x_i ≠ x_j or y_i ≠ y_j (or both).

Then 3 lines follow, i-th line containing 3 numbers f_{i, 1}, f_{i, 2}, f_{i, 3} (0 ≤ f_{i, j} ≤ 1). If f_{i, j} = 1, then it is possible to move the chip j cells backwards from the cell having color i; if f_{i, j} = 0, then such move is impossible.

Output

Print one integer: the number of good colorings, taken modulo 998244353.

Examples

Input


3
3 4 5
2
1 1 1
2 2 2
1 1 1
1 0 0
0 1 1


Output


14346


Input


1
1
1
1 1 1
1 1 1
1 1 1
1 1 1


Output


1


Input


3
1 1 1
1
1 1 1
1 1 1
1 1 1
1 1 1


Output


9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer n, denoting the number of people who needs to be seated, and a list of m integers seats, where 0 represents a vacant seat and 1 represents an already occupied seat.
Find whether all n people can find a seat, provided that no two people can sit next to each other.
Example 1:
Input:
n = 2
m = 7
seats[] = {0, 0, 1, 0, 0, 0, 1}
Output:
Yes
Explanation:
The two people can sit at index 0 and 4.
Example 2:
Input:
n = 1
m = 3
seats[] = {0, 1, 0}
Output:
No
Explanation:
There is no way to get a seat for one person.
Your Task:
You don't have to input or print anything. Complete the function is_possible_to_get_seats() which takes the input parameters and return a boolean value, indicating whether all people can find a seat.
Expected Time Complexity: O(m)
Expected Space Complexity: O(1)
Constraints:
	0 <= n <= 10^{5}
	1 <= m <= 10^{5}
	seats[i] == 0 or seats[i] == 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bidhan studies at the University of Dhaka. Recently he noticed that, some of the university students are speaking a strange language. The words used in that language are not meaningful to him. After some investigation he learned that, the students use the largest lexicographical rotation of words instead of the original words.
 Word p' is a rotation of word p if,
p  = a + b  and
p' = b + a , where a and b are some strings ( possibly empty ) and + sign denotes the concatenation operation.  
w, the largest lexicographical rotation of p is the lexicographically biggest one among all possible p's.

 Given a string, output it's largest lexicographical rotation. 

Input
The only line of the input contains next p.

Output
Output a single line containing the largest lexicographical rotation of p.

Constraints

1 ≤ |p| ≤ 4 × 10^6. ( |p| denotes the size of p. )
p will contain lowercase English letters only.

Example
Input:
bidhan

Output:
nbidha

Explanation
The rotations of string bidhan are 

bidhan,
idhanb,
dhanbi,
hanbid,
anbidh and
nbidha.

nbidha is lexicographically biggest among all of them.

SAMPLE INPUT
bidhan

SAMPLE OUTPUT
nbidha

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a binary matrix  having n rows and m columns, your task is to find the sum of coverage of all zeros in the matrix where coverage for a particular 0 is defined as total number of ones around a zero in left, right, up and bottom directions.
 
Example 1:
Input: matrix = {{0, 1, 0},
{0, 1, 1}, {0, 0, 0}}
Output: 6
Example 2:
Input: matrix = {{0, 1}}
Output: 1
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function FindCoverage() which takes the matrix as input parameter and returns sum of coverage of all zeros in the matrix.
 
Expected Time Complexity: O(n * m)
Expected Space Complexity: O(1)
 
Constraints:
1 <= n, m <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that has been painted last summer should not be painted again.
A neighborhood is a maximal group of continuous houses that are painted with the same color. (For example: houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods  [{1}, {2,2}, {3,3}, {2}, {1,1}]).
Given an array houses, an m * n matrix cost and an integer target where:

houses[i]: is the color of the house i, 0 if the house is not painted yet.
cost[i][j]: is the cost of paint the house i with the color j+1.

Return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods, if not possible return -1.
 
Example 1:
Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 9
Explanation: Paint houses of this way [1,2,2,1,1]
This array contains target = 3 neighborhoods, [{1}, {2,2}, {1,1}].
Cost of paint all houses (1 + 1 + 1 + 1 + 5) = 9.

Example 2:
Input: houses = [0,2,1,2,0], cost = [[1,10],[10,1],[10,1],[1,10],[5,1]], m = 5, n = 2, target = 3
Output: 11
Explanation: Some houses are already painted, Paint the houses of this way [2,2,1,2,2]
This array contains target = 3 neighborhoods, [{2,2}, {1}, {2,2}]. 
Cost of paint the first and last house (10 + 1) = 11.

Example 3:
Input: houses = [0,0,0,0,0], cost = [[1,10],[10,1],[1,10],[10,1],[1,10]], m = 5, n = 2, target = 5
Output: 5

Example 4:
Input: houses = [3,1,2,3], cost = [[1,1,1],[1,1,1],[1,1,1],[1,1,1]], m = 4, n = 3, target = 3
Output: -1
Explanation: Houses are already painted with a total of 4 neighborhoods [{3},{1},{2},{3}] different of target = 3.

 
Constraints:

m == houses.length == cost.length
n == cost[i].length
1 <= m <= 100
1 <= n <= 20
1 <= target <= m
0 <= houses[i] <= n
1 <= cost[i][j] <= 10^4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
$k$ people want to split $n$ candies between them. Each candy should be given to exactly one of them or be thrown away.

The people are numbered from $1$ to $k$, and Arkady is the first of them. To split the candies, Arkady will choose an integer $x$ and then give the first $x$ candies to himself, the next $x$ candies to the second person, the next $x$ candies to the third person and so on in a cycle. The leftover (the remainder that is not divisible by $x$) will be thrown away.

Arkady can't choose $x$ greater than $M$ as it is considered greedy. Also, he can't choose such a small $x$ that some person will receive candies more than $D$ times, as it is considered a slow splitting.

Please find what is the maximum number of candies Arkady can receive by choosing some valid $x$.


-----Input-----

The only line contains four integers $n$, $k$, $M$ and $D$ ($2 \le n \le 10^{18}$, $2 \le k \le n$, $1 \le M \le n$, $1 \le D \le \min{(n, 1000)}$, $M \cdot D \cdot k \ge n$) — the number of candies, the number of people, the maximum number of candies given to a person at once, the maximum number of times a person can receive candies.


-----Output-----

Print a single integer — the maximum possible number of candies Arkady can give to himself.

Note that it is always possible to choose some valid $x$.


-----Examples-----
Input
20 4 5 2

Output
8

Input
30 9 4 1

Output
4



-----Note-----

In the first example Arkady should choose $x = 4$. He will give $4$ candies to himself, $4$ candies to the second person, $4$ candies to the third person, then $4$ candies to the fourth person and then again $4$ candies to himself. No person is given candies more than $2$ times, and Arkady receives $8$ candies in total.

Note that if Arkady chooses $x = 5$, he will receive only $5$ candies, and if he chooses $x = 3$, he will receive only $3 + 3 = 6$ candies as well as the second person, the third and the fourth persons will receive $3$ candies, and $2$ candies will be thrown away. He can't choose $x = 1$ nor $x = 2$ because in these cases he will receive candies more than $2$ times.

In the second example Arkady has to choose $x = 4$, because any smaller value leads to him receiving candies more than $1$ time.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A sequence $a_1, a_2, \dots, a_k$ is called an arithmetic progression if for each $i$ from $1$ to $k$ elements satisfy the condition $a_i = a_1 + c \cdot (i - 1)$ for some fixed $c$.

For example, these five sequences are arithmetic progressions: $[5, 7, 9, 11]$, $[101]$, $[101, 100, 99]$, $[13, 97]$ and $[5, 5, 5, 5, 5]$. And these four sequences aren't arithmetic progressions: $[3, 1, 2]$, $[1, 2, 4, 8]$, $[1, -1, 1, -1]$ and $[1, 2, 3, 3, 3]$.

You are given a sequence of integers $b_1, b_2, \dots, b_n$. Find any index $j$ ($1 \le j \le n$), such that if you delete $b_j$ from the sequence, you can reorder the remaining $n-1$ elements, so that you will get an arithmetic progression. If there is no such index, output the number -1.


-----Input-----

The first line of the input contains one integer $n$ ($2 \le n \le 2\cdot10^5$) — length of the sequence $b$. The second line contains $n$ integers $b_1, b_2, \dots, b_n$ ($-10^9 \le b_i \le 10^9$) — elements of the sequence $b$.


-----Output-----

Print such index $j$ ($1 \le j \le n$), so that if you delete the $j$-th element from the sequence, you can reorder the remaining elements, so that you will get an arithmetic progression. If there are multiple solutions, you are allowed to print any of them. If there is no such index, print -1.


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

Output
4
Input
8
1 2 3 4 5 6 7 8

Output
1
Input
4
1 2 4 8

Output
-1


-----Note-----

Note to the first example. If you delete the $4$-th element, you can get the arithmetic progression $[2, 4, 6, 8]$.

Note to the second example. The original sequence is already arithmetic progression, so you can delete $1$-st or last element and you will get an arithmetical progression again.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A truncatable prime is a prime number which contains no zeros in decimal notation and all its suffixes are primes. 1 is considered to be not a prime.

You are given a positive integer n. Figure out whether it is a truncatable prime.

Input

The only line of input contains an integer n (2 ≤ n ≤ 107).

Output

Output "YES" if n is a truncatable prime. Output "NO" otherwise. Quotes for clarity only.

Examples

Input

19


Output

NO


Input

9137


Output

YES

Note

In the first sample 19 is a prime but its suffix 9 is not.

In the second sample 9137, 137, 37 and 7 are all primes, so 9137 is a truncatable prime.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Have you ever played Hanabi? If not, then you've got to try it out! This problem deals with a simplified version of the game.

Overall, the game has 25 types of cards (5 distinct colors and 5 distinct values). Borya is holding n cards. The game is somewhat complicated by the fact that everybody sees Borya's cards except for Borya himself. Borya knows which cards he has but he knows nothing about the order they lie in. Note that Borya can have multiple identical cards (and for each of the 25 types of cards he knows exactly how many cards of this type he has).

The aim of the other players is to achieve the state when Borya knows the color and number value of each of his cards. For that, other players can give him hints. The hints can be of two types: color hints and value hints. 

A color hint goes like that: a player names some color and points at all the cards of this color. 

Similarly goes the value hint. A player names some value and points at all the cards that contain the value.

Determine what minimum number of hints the other players should make for Borya to be certain about each card's color and value.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100) — the number of Borya's cards. The next line contains the descriptions of n cards. The description of each card consists of exactly two characters. The first character shows the color (overall this position can contain five distinct letters — R, G, B, Y, W). The second character shows the card's value (a digit from 1 to 5). Borya doesn't know exact order of the cards they lie in.


-----Output-----

Print a single integer — the minimum number of hints that the other players should make.


-----Examples-----
Input
2
G3 G3

Output
0

Input
4
G4 R4 R3 B3

Output
2

Input
5
B1 Y1 W1 G1 R1

Output
4



-----Note-----

In the first sample Borya already knows for each card that it is a green three.

In the second sample we can show all fours and all red cards.

In the third sample you need to make hints about any four colors.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Apart from Nian, there is a daemon named Sui, which terrifies children and causes them to become sick. Parents give their children money wrapped in red packets and put them under the pillow, so that when Sui tries to approach them, it will be driven away by the fairies inside.

Big Banban is hesitating over the amount of money to give out. He considers loops to be lucky since it symbolizes unity and harmony.

He would like to find a positive integer *n* not greater than 1018, such that there are exactly *k* loops in the decimal representation of *n*, or determine that such *n* does not exist.

A loop is a planar area enclosed by lines in the digits' decimal representation written in Arabic numerals. For example, there is one loop in digit 4, two loops in 8 and no loops in 5. Refer to the figure below for all exact forms.

Input Specification:
The first and only line contains an integer *k* (1<=≤<=*k*<=≤<=106) — the desired number of loops.

Output Specification:
Output an integer — if no such *n* exists, output -1; otherwise output any such *n*. In the latter case, your output should be a positive decimal integer not exceeding 1018.

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

Demo Output:
['462', '8080']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Problem Statement
Write a function that takes two string parameters, an IP (v4) address and a subnet mask, and returns two strings: the network block, and the host identifier.

The function does not need to support CIDR notation.

# Description
A single IP address with subnet mask actually specifies several addresses: a network block, and a host identifier, and a broadcast address. These addresses can be calculated using a bitwise AND operation on each bit.

(The broadcast address is not used in this kata.)

## Example
A computer on a simple home network might have the following IP and subnet mask:
```
IP: 192.168.2.1
Subnet: 255.255.255.0
(CIDR Notation: 192.168.2.1 /24)
```
In this example, the network block is: **192.168.2.0**. And the host identifier is: **0.0.0.1**. 

## bitwise AND 
To calculate the network block and host identifier the bits in each octet are ANDed together. When the result of the AND operation is '1', the bit specifies a network address (instead of a host address).

To compare the first octet in our example above, convert both the numbers to binary and perform an AND operation on each bit:
```
11000000 (192 in binary)
11111111 (255 in binary)
--------------------------- (AND each bit)
11000000 (192 in binary)
```
So in the first octet, '**192**' is part of the network address. The host identifier is simply '**0**'.

For more information see the [Subnetwork](http://en.wikipedia.org/wiki/Subnetwork) article on Wikipedia.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string $s$ consisting of $n$ characters. Each character of $s$ is either 0 or 1.

A substring of $s$ is a contiguous subsequence of its characters.

You have to choose two substrings of $s$ (possibly intersecting, possibly the same, possibly non-intersecting — just any two substrings). After choosing them, you calculate the value of the chosen pair of substrings as follows:

let $s_1$ be the first substring, $s_2$ be the second chosen substring, and $f(s_i)$ be the integer such that $s_i$ is its binary representation (for example, if $s_i$ is 11010, $f(s_i) = 26$);

the value is the bitwise OR of $f(s_1)$ and $f(s_2)$.

Calculate the maximum possible value you can get, and print it in binary representation without leading zeroes.


-----Input-----

The first line contains one integer $n$ — the number of characters in $s$.

The second line contains $s$ itself, consisting of exactly $n$ characters 0 and/or 1.

All non-example tests in this problem are generated randomly: every character of $s$ is chosen independently of other characters; for each character, the probability of it being 1 is exactly $\frac{1}{2}$.

This problem has exactly $40$ tests. Tests from $1$ to $3$ are the examples; tests from $4$ to $40$ are generated randomly. In tests from $4$ to $10$, $n = 5$; in tests from $11$ to $20$, $n = 1000$; in tests from $21$ to $40$, $n = 10^6$.

Hacks are forbidden in this problem.


-----Output-----

Print the maximum possible value you can get in binary representation without leading zeroes.


-----Examples-----

Input
5
11010
Output
11111
Input
7
1110010
Output
1111110
Input
4
0000
Output
0


-----Note-----

In the first example, you can choose the substrings 11010 and 101. $f(s_1) = 26$, $f(s_2) = 5$, their bitwise OR is $31$, and the binary representation of $31$ is 11111.

In the second example, you can choose the substrings 1110010 and 11100.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr[ ] of n integers, for every element, find the closest element on it's right that has a greater frequency than its own frequency.
Frequency is the number of times the element appears in the array.
 
Example 1:
Input:
n = 6
arr[] = {2 1 1 3 2 1}
Output:
1 -1 -1 2 1 -1 
Explanation:
1 appears 3 times.
2 appears 2 times.
3 appears 1 time. 
For arr[0] ie, 2
arr[1] ie 1 is the closest element on its 
right which has greater frequency than the 
frequency of 2. For the arr[1] and arr[2] no element 
on the right has greater frequency than 1, 
so -1 will be printed. and so on. 
Example 2:
Input:
n = 10
arr[] = {5 1 2 3 2 5 5 4 5 2}
Output:
-1 2 5 2 5 -1 -1 5 -1 -1
 
Your task:
Your task is to complete the function print_next_greater_freq() which take two parameters arr and n.This function returns answer(as a list of integers) as explained above.
Expected time complexity: O(n)
Expected space complexity: O(n)
Constraints:
1 <= n <= 10^{4}
1 <= arr[i] <= 10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are going to the beach with the idea to build the greatest sand castle ever in your head! The beach is not as three-dimensional as you could have imagined, it can be decribed as a line of spots to pile up sand pillars. Spots are numbered 1 through infinity from left to right. 

Obviously, there is not enough sand on the beach, so you brought n packs of sand with you. Let height h_{i} of the sand pillar on some spot i be the number of sand packs you spent on it. You can't split a sand pack to multiple pillars, all the sand from it should go to a single one. There is a fence of height equal to the height of pillar with H sand packs to the left of the first spot and you should prevent sand from going over it. 

Finally you ended up with the following conditions to building the castle:  h_1 ≤ H: no sand from the leftmost spot should go over the fence;  For any $i \in [ 1 ; \infty)$ |h_{i} - h_{i} + 1| ≤ 1: large difference in heights of two neighboring pillars can lead sand to fall down from the higher one to the lower, you really don't want this to happen;  $\sum_{i = 1}^{\infty} h_{i} = n$: you want to spend all the sand you brought with you. 

As you have infinite spots to build, it is always possible to come up with some valid castle structure. Though you want the castle to be as compact as possible. 

Your task is to calculate the minimum number of spots you can occupy so that all the aforementioned conditions hold.


-----Input-----

The only line contains two integer numbers n and H (1 ≤ n, H ≤ 10^18) — the number of sand packs you have and the height of the fence, respectively.


-----Output-----

Print the minimum number of spots you can occupy so the all the castle building conditions hold.


-----Examples-----
Input
5 2

Output
3

Input
6 8

Output
3



-----Note-----

Here are the heights of some valid castles:   n = 5, H = 2, [2, 2, 1, 0, ...], [2, 1, 1, 1, 0, ...], [1, 0, 1, 2, 1, 0, ...]  n = 6, H = 8, [3, 2, 1, 0, ...], [2, 2, 1, 1, 0, ...], [0, 1, 0, 1, 2, 1, 1, 0...] (this one has 5 spots occupied) 

The first list for both cases is the optimal answer, 3 spots are occupied in them.

And here are some invalid ones:  n = 5, H = 2, [3, 2, 0, ...], [2, 3, 0, ...], [1, 0, 2, 2, ...]  n = 6, H = 8, [2, 2, 2, 0, ...], [6, 0, ...], [1, 4, 1, 0...], [2, 2, 1, 0, ...]

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