ICPC 2022-2023 NERC (NEERC), Southern and Volga Russia Qualifier
A. As Fast As Possible
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Monocarp plays a new computer game. Each level of this game can be represented as the coordinate axis $$$oX$$$.

To beat the current level, Monocarp's character has to travel from the point $$$0$$$ to the point $$$n$$$. There are two ways to move in the game:

  • walk to an adjacent point; it takes $$$a$$$ seconds (i. e. move from $$$x$$$ to $$$x - 1$$$ or $$$x + 1$$$ in $$$a$$$ seconds);
  • jump to a point with distance $$$d$$$ from the current one; the leap takes $$$b$$$ seconds (i. e. move from $$$x$$$ to $$$x - d$$$ or $$$x + d$$$ in $$$b$$$ seconds).

Note that it's possible that Monocarp's character will travel through some points that are to the left of point $$$0$$$ or to the right of point $$$n$$$; it's not against the rules, since the level is infinite.

You have to calculate the minimum time required to reach the point $$$n$$$ from the point $$$0$$$.

Input

The first line contains four integers $$$n$$$, $$$a$$$, $$$b$$$ and $$$d$$$ ($$$1 \le n \le 1\,000$$$, $$$1 \le a \le 1\,000$$$, $$$1 \le b \le 1\,000$$$, $$$1 \le d \le n$$$) — the point Monocarp's character has to reach, the time required to walk to an adjacent point, the time required to leap, and the length of the leap.

Output

Print one integer — the minimum time required to reach the point $$$n$$$ from the point $$$0$$$.

Examples
Input
9 7 6 5
Output
19
Input
20 5 10 15
Output
35
Input
4 3 5 2
Output
10
Note

In the first example, it's possible to walk to the left for $$$7$$$ seconds. Then Monocarp's character ends up in the point $$$-1$$$. Then he can leap to the right twice, the first leap ends in the point $$$4$$$, and the second leap ends in the point $$$9$$$. Two leaps take $$$12$$$ seconds. So, Monocarp reaches the goal in $$$7 + 12 = 19$$$ seconds.

In the second example, it's possible to start by leaping to the right. Then the character ends up in the point $$$15$$$, spending $$$10$$$ seconds. Then he has to walk to the right $$$5$$$ times, so he reaches the point $$$20$$$. The total time spent by Monocarp will be equal to $$$10 + 5 \cdot 5 = 35$$$ seconds.

In the third example, it's possible to leap to the right twice. Then the character ends up in the point $$$4$$$, spending $$$10$$$ seconds.

B. Permutation Value
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. You have to construct a permutation of size $$$n$$$.

A permutation is an array where each integer from $$$1$$$ to $$$s$$$ (where $$$s$$$ is the size of permutation) occurs exactly once. For example, $$$[2, 1, 4, 3]$$$ is a permutation of size $$$4$$$; $$$[1, 2, 4, 5, 3]$$$ is a permutation of size $$$5$$$; $$$[1, 4, 3]$$$ is not a permutation (the integer $$$2$$$ is absent), $$$[2, 1, 3, 1]$$$ is not a permutation (the integer $$$1$$$ appears twice).

A subsegment of a permutation is a contiguous subsequence of that permutation. For example, the permutation $$$[2, 1, 4, 3]$$$ has $$$10$$$ subsegments: $$$[2]$$$, $$$[2, 1]$$$, $$$[2, 1, 4]$$$, $$$[2, 1, 4, 3]$$$, $$$[1]$$$, $$$[1, 4]$$$, $$$[1, 4, 3]$$$, $$$[4]$$$, $$$[4, 3]$$$ and $$$[3]$$$.

The value of the permutation is the number of its subsegments which are also permutations. For example, the value of $$$[2, 1, 4, 3]$$$ is $$$3$$$ since the subsegments $$$[2, 1]$$$, $$$[1]$$$ and $$$[2, 1, 4, 3]$$$ are permutations.

You have to construct a permutation of size $$$n$$$ with minimum possible value among all permutations of size $$$n$$$.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 48$$$) — the number of test cases.

Then, $$$t$$$ lines follow. The $$$i$$$-th of them contains one integer $$$n$$$ ($$$3 \le n \le 50$$$) representing the $$$i$$$-th test case.

Output

For each test case, print $$$n$$$ integers — the permutation of size $$$n$$$ with minimum possible value. If there are multiple such permutations, print any of them.

Example
Input
2
5
6
Output
1 4 3 5 2
4 1 6 2 5 3
Note

In the first example, the permutation $$$[1, 4, 3, 5, 2]$$$ is one of the possible answers; its value is $$$2$$$.

In the second example, the permutation $$$[4, 1, 6, 2, 5, 3]$$$ is one of the possible answers; its value is $$$2$$$.

C. Reverse and Remove
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Monocarp has a string $$$s$$$ of length $$$n$$$. The string consists of characters a and/or b.

Monocarp will apply the following operation to this string $$$k$$$ times ($$$2k \lt n$$$):

  1. if the first character of the string is different from the last character, then Monocarp reverses the string (so the first character becomes the last one, the second character becomes the second-to-last one, and so on);
  2. no matter what happens during the first step, Monocarp removes the first character and the last character.

You have to print the resulting string after these $$$k$$$ operations. Note that the constraints on $$$k$$$ guarantee that at least one character will remain in the string.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$3 \le n \le 200\,000$$$, $$$1 \le k$$$, $$$2k \lt n$$$) — the length of the string and the number of operations Monocarp performes, respectively.

The second line contains the string $$$s$$$ consisting of $$$n$$$ characters a and/or b.

Output

Print the resulting string after $$$k$$$ operations are performed.

Examples
Input
6 2
ababbb
Output
ba
Input
13 4
bababbaaababb
Output
aaabb
Input
8 2
abaaabab
Output
aaab
Input
7 1
ababbab
Output
abbab
Input
3 1
bba
Output
b
Input
6 1
aababa
Output
abab
Note

In the first example, during the first operation, the string is reversed, so it becomes bbbaba. Then the first character and the last character are removed, so it becomes bbab. The string won't be reversed during the second operation, and after removing the first and the last character, it becomes ba.

D. Password
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Monocarp has forgotten the password to his mobile phone. The password consists of $$$6$$$ digits from $$$0$$$ to $$$9$$$ (note that it can start with the digit $$$0$$$).

Monocarp remembers that his password had exactly two different digits, and each of these digits appeared exactly three times in the password. Monocarp also remembers some digits which were definitely not used in the password.

You have to calculate the number of different sequences of $$$6$$$ digits that could be the password for Monocarp's mobile phone (i. e. these sequences should meet all of the constraints on Monocarp's password).

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 8$$$) — the number of digits for which Monocarp remembers that they were not used in the password.

The second line contains $$$n$$$ different integers $$$a_1, a_2, \dots a_n$$$ ($$$0 \le a_i \le 9$$$) representing the digits that were not used in the password. Note that the digits $$$a_1, a_2, \dots, a_n$$$ are given in ascending order.

Output

Print one integer — the number of different $$$6$$$-digit sequences that meet the constraints.

Examples
Input
8
0 1 2 4 5 6 8 9
Output
20
Input
1
8
Output
720

E. d-Sort
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Monocarp has got a sequence of integers $$$a_1, a_2, \dots, a_n$$$. He can perform the following operation any number of times:

  • choose two indices $$$i$$$ and $$$j$$$ ($$$i \lt j$$$) having distance exactly $$$d$$$ (i. e. $$$j - i = d$$$), and swap the corresponding elements of the sequence, i. e. swap $$$a_i$$$ and $$$a_j$$$.

You have to determine if it is possible to sort the sequence in non-descending order (i. e. reorder the elements so that for each $$$i$$$ from $$$1$$$ to $$$n - 1$$$, the condition $$$a_i \le a_{i + 1}$$$ is met) using the described operation any number of times (possibly zero).

Input

The first line contains two integers $$$n$$$ and $$$d$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le d \le n - 1$$$) — the number of elements in the sequence and the distance for the swap operation, respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$) — the elements of the sequence.

Output

If it's possible to sort the sequence in non-descending order using the described operation any number of times, print YES. Otherwise, print NO.

Examples
Input
4 2
6 7 1 4
Output
YES
Input
5 3
5 6 6 10 10
Output
YES
Input
8 3
4 5 3 1 3 4 2 4
Output
NO
Note

In the first example, it's possible to swap the first element and the third element (the sequence becomes $$$[1, 7, 6, 4]$$$), and then swap the second element and the fourth element (so the sequence becomes $$$[1, 4, 6, 7]$$$). After that, the sequence is sorted in non-descending order.

In the second example, the sequence is already sorted in non-descending order.

F. Save the Magazines
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Monocarp has been collecting rare magazines for quite a while, and now he has decided to cell them. He distributed the magazines between $$$n$$$ boxes, arranged in a row. The $$$i$$$-th box contains $$$a_i$$$ magazines. Some of the boxes are covered with lids, others are not.

Suddenly it started to rain, and now Monocarp has to save as many magazines from the rain as possible. To do this, he can move the lids between boxes as follows: if the $$$i$$$-th box was covered with a lid initially, he can either move the lid from the $$$i$$$-th box to the box $$$(i-1)$$$ (if it exists), or keep the lid on the $$$i$$$-th box. You may assume that Monocarp can move the lids instantly at the same moment, and no lid can be moved more than once. If a box will be covered with a lid after Monocarp moves the lids, the magazines in it will be safe from the rain; otherwise they will soak.

You have to calculate the maximum number of magazines Monocarp can save from the rain.

Input

The first line contains one integer $$$n$$$ ($$$1 \le n \le 200\,000$$$) — the number of boxes.

The second line contains a string of $$$n$$$ characters 0 and/or 1. If the $$$i$$$-th character is 1, the $$$i$$$-th box is initially covered with a lid. If the $$$i$$$-th character is 0, the $$$i$$$-th box is initially not covered.

The third line contains a sequence of integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$), where $$$a_i$$$ is the number of magazines in the $$$i$$$-th box.

Output

Print one integer — the maximum number of magazines Monocarp can save from the rain.

Examples
Input
5
01110
10 5 8 9 6
Output
27
Input
6
011011
20 10 9 30 20 19
Output
80
Input
4
0000
100 100 100 100
Output
0
Input
4
0111
5 4 5 1
Output
14
Note

In the first example, Monocarp can move the lid from the second box to the first box, so the boxes $$$1$$$, $$$3$$$ and $$$4$$$ are covered, and $$$10 + 8 + 9 = 27$$$ magazines are saved.

In the second example, Monocarp can move the lid from the second box to the first box, then from the third box to the second box, then from the fifth box to the fourth box, and then from the sixth box to the fifth box. The boxes $$$1$$$, $$$2$$$, $$$4$$$ and $$$5$$$ will be covered, so $$$20 + 10 + 30 + 20 = 80$$$ magazines can be saved.

There are no lids in the third example, so it's impossible to save even a single magazine.

G. Scoring
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Monocarp is participating in a competition. There are $$$n$$$ judges evaluating the participants; the score given by each of them is an integer between $$$1$$$ and $$$10^{9}$$$, inclusive (the bigger it is, the better for the participant).

According to the rules of the competition, the final score of the participant is an integer, which is calculated based on the list of $$$n$$$ integers given by the judges, as follows:

  • let $$$x$$$ be the minimum of the scores in the list, and $$$y$$$ be the maximum of the scores in the list. Both $$$x$$$ and $$$y$$$ are removed from the list (note that if there are multiple occurrences of the minimum/maximum in the list, only one of them is removed); then, the number $$$\frac{x + y}{2}$$$, rounded down to the nearest integer, is added to the list.

This operation is performed $$$n - 1$$$ times, after which, the list contains only one number. The remaining integer is the final score of the participant.

You have to calculate Monocarp's final score according to these rules, based on the score he received from each judge.

Input

The first line contains one integer $$$n$$$ ($$$2 \le n \le 200\,000$$$) — the number of judges.

The second line contains the sequence of integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$) — the scores given by the judges.

Output

Print one integer — the final score calculated according to the rules of the competition.

Examples
Input
5
3 6 1 9 1
Output
3
Input
8
12 12 40 30 20 24 21 13
Output
20
Input
3
100 100 100
Output
100
Note

The sorted list of the scores in the first example is $$$[1, 1, 3, 6, 9]$$$.

During the first operation, $$$x = 1$$$, $$$y = 9$$$. These integers are removed, and $$$\frac{1 + 9}{2} = 5$$$ is added. So, the current list is $$$[1, 3, 5, 6]$$$.

During the second operation, $$$x = 1$$$, $$$y = 6$$$. These integers are removed, and $$$\frac{1 + 6}{2} = 3$$$ (rounded down) is added. So, the current list is $$$[3, 3, 5]$$$.

During the third operation, $$$x = 3$$$, $$$y = 5$$$. These integers are removed, and $$$\frac{3 + 5}{2} = 4$$$ is added. So, the current list is $$$[3, 4]$$$.

During the fourth operation, $$$x = 3$$$, $$$y = 4$$$. These integers are removed, and $$$\frac{3 + 4}{2} = 3$$$ (rounded down) is added. So, the current list is $$$[3]$$$.

The final score is $$$3$$$, since it is the only element of the resulting list.

H. Report Preparation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Monocarp is a student. There are $$$n$$$ other students in his group at the university.

The Linguistics lecturer told the students to prepare a report based on a book which consists of $$$m$$$ pages. Pages of the book are numbered from $$$1$$$. The group of students will be prepared for the report if every page of the book is read by at least one student.

The $$$i$$$-th student from $$$n$$$ of Monocarp's groupmates (excluding Monocarp himself) has read several pages of the book, from the page $$$a_i$$$ to the page $$$b_i$$$ inclusive ($$$a_i \le b_i$$$).

Monocarp will read several consecutive (without skips) pages of the book — he thinks that it will allow him to prepare better. You have to calculate the minimum number of pages he has to read so that the group is prepared for the report (i. e. so that every page is read by at least one student).

Note that if every page of the book is already read by at least one student, Monocarp won't read anything.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 200\,000$$$, $$$1 \le m \le 10^{9}$$$) — the number of students (excluding Monocarp) and the number of pages in the book, respectively.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le b_i \le m$$$) — the first and the last page in the part of the book which was read by the $$$i$$$-th student. So, the $$$i$$$-th student has read all pages from the $$$a_i$$$-th one to the $$$b_i$$$-th one inclusive.

Output

Print one integer — the minimum number of pages Monocarp has to read so that every page is read by at least one student. If Monocarp doesn't have to read anything, print $$$0$$$.

Examples
Input
2 6
1 2
5 6
Output
2
Input
3 10
2 7
5 8
9 9
Output
10
Input
2 15
1 13
4 15
Output
0
Note

In the first example, Monocarp has to read the third page and the fourth page, and the group will be prepared for the report.

In the second example, neither the first page nor the last page has been read. Since Monocarp cannot skip pages while reading, he has to read all $$$10$$$ pages of the book.

In the third example, Monocarp doesn't have to read anything, since each page is already read by some other student.

I. Lanterns
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Monocarp lives on a street which can be represented as a segment of the $$$oX$$$ axis. The street begins in point $$$0$$$ and ends in point $$$f$$$. There are $$$n$$$ pillars on the street, they are located in points $$$a_1, a_2, \dots, a_n$$$.

It is possible to install a lantern on each pillar. Each lantern illuminates a segment of the axis. If a lantern is installed on a pillar in point $$$x$$$, and the power of the lantern is $$$y$$$, then the segment from $$$x - y$$$ to $$$x + y$$$ (including both endpoints) will be illuminated.

Monocarp can install up to $$$k$$$ lanterns. Each lantern's power should be a positive integer.

Monocarp wants to illuminate the whole street, i. e. each point from $$$0$$$ to $$$f$$$. Note that all points from $$$0$$$ to $$$f$$$, including non-integer ones, should be illuminated.

To achieve this, Monocarp will choose $$$k$$$ pillars, install lanterns on them (one lantern on each of the chosen pillars), and tune all lanterns, so they have the same power, equal to $$$d$$$.

Monocarp doesn't want to spend too much money on electricity (the more power the lantern has, the more it consumes). Help him calculate the minimum possible power for his $$$k$$$ lanterns, so they can be installed in such a way that the whole street (from $$$0$$$ to $$$f$$$) is illuminated.

Input

The first line contains three integers $$$n$$$, $$$k$$$ and $$$f$$$ ($$$1 \le k \le n \le 200\,000$$$, $$$1 \le f \le 10^{9}$$$) — the number of pillars, the number of lanterns and the rightmost point of the street, respectively.

The second line contains the sequence of integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le f$$$) — the locations of the lanterns. The elements of the sequence are pairwise distinct.

Output

Print one integer — the minimum possible power of lanterns (all $$$k$$$ lanterns should have the same power) such that $$$k$$$ lanterns are enough to illuminate the whole street from the point $$$0$$$ to the point $$$f$$$ (including non-integer points).

Examples
Input
2 1 12
6 4
Output
6
Input
4 2 20
3 6 13 19
Output
7
Input
2 2 1
0 1
Output
1
Input
2 1 1
0 1
Output
1
Input
10 4 100
34 52 12 35 89 60 77 43 23 11
Output
15
Note

In the first example, it is possible to install a lantern with power $$$6$$$ on a pillar in point $$$6$$$. Then all points from $$$0$$$ to $$$12$$$ will be illuminated.

In the second example, it is possible to install the lanterns in points $$$3$$$ and $$$13$$$ with power $$$7$$$. Then all points from $$$0$$$ to $$$20$$$ will be illuminated. Note that the lantern in point $$$3$$$ will illuminate the segment $$$[-4, 10]$$$, which is partially outside the street, but it doesn't make the placement incorrect.

In the third example, Monocarp has to install the lanterns on both pillars with power $$$1$$$, since all points (including non-integer ones) should be illuminated, and the power of the lanterns should be integer.

In the fourth example, the lantern with power $$$1$$$ can be installed on any pillar. All points from $$$0$$$ to $$$1$$$ will be illuminated.

J. Problem with Random Tests
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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$$$.

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.

K. FTL
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Monocarp is playing a video game. In the game, he controls a spaceship and has to destroy an enemy spaceship.

Monocarp has two lasers installed on his spaceship. Both lasers $$$1$$$ and $$$2$$$ have two values:

  • $$$p_i$$$ — the power of the laser;
  • $$$t_i$$$ — the reload time of the laser.

When a laser is fully charged, Monocarp can either shoot it or wait for the other laser to charge and shoot both of them at the same time.

An enemy spaceship has $$$h$$$ durability and $$$s$$$ shield capacity. When Monocarp shoots an enemy spaceship, it receives $$$(P - s)$$$ damage (i. e. $$$(P - s)$$$ gets subtracted from its durability), where $$$P$$$ is the total power of the lasers that Monocarp shoots (i. e. $$$p_i$$$ if he only shoots laser $$$i$$$ and $$$p_1 + p_2$$$ if he shoots both lasers at the same time). An enemy spaceship is considered destroyed when its durability becomes $$$0$$$ or lower.

Initially, both lasers are zero charged.

What's the lowest amount of time it can take Monocarp to destroy an enemy spaceship?

Input

The first line contains two integers $$$p_1$$$ and $$$t_1$$$ ($$$2 \le p_1 \le 5000$$$; $$$1 \le t_1 \le 10^{12}$$$) — the power and the reload time of the first laser.

The second line contains two integers $$$p_2$$$ and $$$t_2$$$ ($$$2 \le p_2 \le 5000$$$; $$$1 \le t_2 \le 10^{12}$$$) — the power and the reload time of the second laser.

The third line contains two integers $$$h$$$ and $$$s$$$ ($$$1 \le h \le 5000$$$; $$$1 \le s \lt \min(p_1, p_2)$$$) — the durability and the shield capacity of an enemy spaceship. Note that the last constraint implies that Monocarp will always be able to destroy an enemy spaceship.

Output

Print a single integer — the lowest amount of time it can take Monocarp to destroy an enemy spaceship.

Examples
Input
5 10
4 9
16 1
Output
20
Input
10 1
5000 100000
25 9
Output
25
Note

In the first example, Monocarp waits for both lasers to charge, then shoots both lasers at $$$10$$$, they deal $$$(5 + 4 - 1) = 8$$$ damage. Then he waits again and shoots lasers at $$$20$$$, dealing $$$8$$$ more damage.

In the second example, Monocarp doesn't wait for the second laser to charge. He just shoots the first laser $$$25$$$ times, dealing $$$(10 - 9) = 1$$$ damage each time.

L. Intersection and Union
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given $$$n$$$ segments on the coordinate axis. The $$$i$$$-th segment is $$$[l_i, r_i]$$$. Let's denote the set of all integer points belonging to the $$$i$$$-th segment as $$$S_i$$$.

Let $$$A \cup B$$$ be the union of two sets $$$A$$$ and $$$B$$$, $$$A \cap B$$$ be the intersection of two sets $$$A$$$ and $$$B$$$, and $$$A \oplus B$$$ be the symmetric difference of $$$A$$$ and $$$B$$$ (a set which contains all elements of $$$A$$$ and all elements of $$$B$$$, except for the ones that belong to both sets).

Let $$$[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$$$ be an array where each element is either $$$\cup$$$, $$$\oplus$$$, or $$$\cap$$$. Over all $$$3^{n-1}$$$ ways to choose this array, calculate the sum of the following values:

$$$$$$|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$$$$$$

In this expression, $$$|S|$$$ denotes the size of the set $$$S$$$.

Input

The first line contains one integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$).

Then, $$$n$$$ lines follow. The $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i \le r_i \le 3 \cdot 10^5$$$).

Output

Print one integer — the sum of $$$|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$$$ over all possible ways to choose $$$[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$$$. Since the answer can be huge, print it modulo $$$998244353$$$.

Examples
Input
4
3 5
4 8
2 2
1 9
Output
162
Input
4
1 9
3 5
4 8
2 2
Output
102

M. Antifibonacci Cut
time limit per test
12 seconds
memory limit per test
4 megabytes
input
standard input
output
standard output

Note that the memory limit is unusual.

Let's define the sequence of Fibonacci strings as follows: $$$f_0$$$ is 0, $$$f_1$$$ is 1, $$$f_i$$$ is $$$f_{i-1} + f_{i-2}$$$ for $$$i \gt 1$$$ ($$$+$$$ denotes the concatenation of two strings). So, for example, $$$f_2$$$ is 10, $$$f_3$$$ is 101, $$$f_4$$$ is 10110.

For a given string $$$s$$$, let's define $$$g(s)$$$ as the number of ways to cut it into several (any number, possibly even just one) strings such that none of these strings are Fibonacci strings. For example, if $$$s$$$ is 10110101, $$$g(s) = 3$$$ since there are three ways to cut it:

  • 101101 $$$+$$$ 01;
  • 1011 $$$+$$$ 0101;
  • 1011 $$$+$$$ 01 $$$+$$$ 01.

You are given a sequence of strings $$$s_1, s_2, \dots, s_n$$$. Calculate $$$g(s_1), g(s_1 + s_2), \dots, g(s_1 + s_2 + \ldots + s_n)$$$. Since these values can be huge, print them modulo $$$998244353$$$.

Input

The first line of the input contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^3$$$).

Then, $$$n$$$ lines follow. The $$$i$$$-th line contains the string $$$s_i$$$ ($$$1 \le |s_i| \le 10^3$$$), consisting of characters 0 and/or 1.

Output

Print $$$n$$$ integers, where the $$$i$$$-th integer is $$$g(s_1 + s_2 + \ldots + s_i) \bmod 998244353$$$.

Examples
Input
1
10110101
Output
3
Input
3
1111
1
0
Output
2
3
3
Input
6
10110101
100100001110
0000001100010001
1111
1001010100101010101001
000100000010101111
Output
3
561
1466229
9887505
972227653
52128355