For the new infectious disease, COVID-99, numbers of new positive cases of PCR tests conducted in the city are reported daily. You are requested by the municipal public relations department to write a program that counts the number of the peaks so far of the positive cases.

Here, the number of peaks is the number of days on which the number of positive cases reported is more than both of the day before and the next day.

As the PCR tests started before the disease started spreading in the city, the number of positive cases is zero on the first day. The last reported day is not counted as a peak. No two consecutive days have the same number of positive cases.

The input consists of multiple datasets. Each dataset is in the following format.

n
v₁ ... v_n

n is the number of days on which the numbers of positive cases are reported (3 ≤ n ≤ 1000). v_i is the number of positive cases on the i-th day, an integer between zero and 1000, inclusive. Note that v₁ is zero, and v_i ≠ v_i+1 for 1 ≤ i < n, as stated above.

The end of the input is indicated by a line containing a zero. The input consists of at most 100 datasets.

For each dataset, output the number of peaks in a line.

3
0 1000 0
5
0 1 2 0 1
3
0 1 2
7
0 1 0 1 8 7 6
11
0 4 3 7 6 10 7 8 4 6 10
0

1
1
0
2
4

A card game similar to Old Maid is played by n players P₁, ..., and P_n, sitting clockwise in this order.

For this game, n pairs of cards numbered 1 through n are used. Each player has two cards at hand to start with.

First, any player who has a pair of cards with the same number discards them. If by chance all the players discard the cards in hand, the game ends. Otherwise, the following actions are repeated until the game ends. Note that, from now on, for a player p, the next player means the player closest to p in the clockwise direction among those who still have one or more cards at that point in time.

• Choose the player p as follows.
  • For the first turn, choose P₁. If, however, P₁ has no cards, choose the next player of P₁.
  • For the second and subsequent turns, choose the next player of the one chosen for the previous turn.
• The next player of p, say p′, looks at the card(s) in the hand of p and draws the one having the smallest number among them.
• If that makes a pair of cards with the same number in the hand of p′, the pair is discarded. If no cards remain in any players' hands at this point, the game ends.

Figure B-1 shows the initial hands of the three players of the second dataset in Sample Input. Immediately after, the player P₁ discards the two cards in the hand. p of the first turn is P₂ because P₁ has no cards.

Figure B-2 shows the hands of the five players of the last dataset in Sample Input after the following actions:

• P₁ is chosen first and the next player of P₁, that is, P₂, draws the card with the smallest number 1 from the P₁'s hand. P₂ has three cards with numbers 1, 3, and 5 in hand at the end of this turn;
• P₃, P₄, and P₅, in this order, draw the same card with the number 1 that was initially in the P₁'s hand; and
• P₅ discards the pair of cards with the number 1.

After this, P₁ draws the only remaining card in P₅'s hand and discards the drawn card and the card with the same number 2 in the hand. The player to be drawn from the hand next is the next player of P₅, which is P₂ because P₁'s hand is empty now.

Since at least one pair of cards is discarded between two drawings from the hand of the same player, the game will end sooner or later. Unlike Old Maid, no cards will be left in the hand of any player at the end.

Write a program that, for given initial hands of all the players, computes the number of times cards are drawn by the end of the game.

The input consists of multiple datasets, each in the following format.

n
c_1,1 c_1,2
⋮
c_n,1 c_n,2

n is the number of players. n is an integer no less than two and no more than 1000. c_i,1 and c_i,2 are the numbers on the two cards in the initial hand of P_i (1 ≤ i ≤ n). Each integer between 1 and n, inclusive, appears exactly twice in c_1,1, c_1,2, ..., c_n,1, and c_n,2.

The end of the input is indicated by a line containing a zero. The input has at most 10000 lines.

For each dataset, output a single line containing the integer that is the number of times cards are drawn.

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

0
2
3
14
8
8

With little time remaining until ICPC, you decided to reschedule your training plan. As maintaining both mental and physical vitality is important, you decided to spend n days of the remaining n + m days for training, and m days for repose. The question is which days should be used for the training and which for the repose. A schedule that increases your ICPC power more is better.

Training days increase the power, and consecutive training days are more effective. One day of training on the k-th day of consecutive training days increases the power by 2k − 1, where k = 1 for the first day of the consecutive training days. A single training day increases the power by only 1, but two consecutive training days increase it by 1 + 3 = 4, and three consecutive training days increase it by 1 + 3 + 5 = 9.

Repose days, on the other hand, decrease the power, and consecutive repose days decrease it more rapidly. One day of repose on the k-th day of consecutive repose days decreases the power by 2k − 1, where k = 1 for the first day of the consecutive repose days. A single repose day decreases the power by only 1, but two consecutive repose days decrease it by 1 + 3 = 4, and three consecutive repose days decrease it by 1 + 3 + 5 = 9.

Let us compute the largest increment of your ICPC power after n + m days of training and repose by the best training schedule. Note that, if you have too many repose days, this may be negative.

The input consists of multiple datasets, each in the following format.

n m

Here, n and m are the numbers of training and repose days, respectively. Neither of them exceeds 10⁶, and at least one of them is non-zero.

The end of the input is indicated by a line containing two zeros. The number of datasets does not exceed 100.

For each of the datasets, output in a line the largest increment of ICPC power after n + m days of training and repose by the best training schedule.

1 1
3 2
6 1
1 6
0 3
2 4
7 9
0 0

0
7
35
-17
-9
-4
10

You are working as a staff member at a concert venue, organizing the audience queue. Everyone in the queue holds one ticket with a seat number printed. The seat numbers are integers from 1 to n without duplicates. Since this is a very popular concert, all the seats are reserved and exactly n people are in a single line.

Your job is to split the line at some points and navigate each of the sublines to a distinct entrance gate. The audience are so polite that the order in each of the sublines is kept. There are k entrance gates, and thus you can split the line into k or less sublines. Sublines may have widely varying lengths, but empty sublines are not allowed. In the example of the figure below, the original line [4 2 3 5 1] has been split into three sublines, [4 2], [3 5], and [1].

Although up to k lines are formed, the audience can enter the hall one at a time. Among those who head the lines, one with the smallest seat number enters the hall first. In the example figure below, among the heads 4, 3, and 1 of the lines, one with the smallest seat number, 1, enters the hall first. Subsequent entrance order is decided in the same way. Among those who head the lines at the time, one with the smallest seat number is the next to enter the hall.

The order of entrance depends on how you split the audience line. Different ways of splitting may result in the same order. For the example above, splitting into [4 2], [3], [5], and [1] results in the same order.

Given the initial order in the queue and the final entrance order of the audience, please compute how many different ways of splitting the line result in the given final entrance order. For the same partitioning of the line, different assignments of sublines to gates are not counted separately.

The input consists of multiple datasets, each in the following format.

n k
s₁ ... s_n
t₁ ... t_n

Integers n and k satisfies 1 ≤ k ≤ n ≤ 10⁴. The number of the people in the audience line is represented by n, and the number of the gates is represented by k. The sequence s₁ ... s_n is a permutation of the integers 1 through n, which describes the initial order of the audience in the queue. The sequence t₁ ... t_n is also a permutation of the integers 1 through n, which describes the final entrance order.

The end of the input is indicated by a line "0 0". The number of datasets does not exceed 50.

For each dataset, output in a line the number of ways to split the line as described in the problem statement. Since the number can be very large, the output should be the number modulo the prime number 998 244 353.

5 4
4 2 3 5 1
1 3 4 2 5
3 3
1 2 3
1 2 3
3 2
3 2 1
1 2 3
7 5
4 5 6 7 1 2 3
1 2 3 4 5 6 7
4 4
2 1 4 3
1 4 3 2
31 31
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
0 0

2
4
0
26
0
75497471

Icpca village, said to lie in a deep jungle, is known by strange, contradictory lore. Some say there lies a epitome of happiness while others say it is a terrible fortress of horror.

An old soothsayer, who is a precious source of information, reported that Icpca village has a rectangular form with streets of a grid pattern. n west-east straight streets and m north-south straight streets pass through the village. n and m are both even. To investigate the reality of the lore, a team of n + m researchers were sent to Icpca village. The plan of the investigation was as follows.

• The i-th of the first n researchers walks from the western end to the eastern end on the i-th street from the north.
• The j-th of the remaining m researchers walks from the northern end to the southern end on the j-th street from the west.

Some of the researchers returned from Icpca village as planned. However, nothing has been heard from the rest...

According to the pseudopsia of the old soothsayer, there stands exactly one statue on each of the nm intersections of west-east and north-south streets in Icpca village. Each statue is either beautiful or horrible.

Each researcher has a value called sanity. All the researchers have the sanity of 0 before they start the investigation. When a researcher comes to an intersection with a beautiful statue, his/her sanity is increased by 1. When a researcher comes to an intersection with a horrible statue, his/her sanity is decreased by 1. Since the horrible statues are extraordinarily horrible, if the sanity of a researcher becomes negative, he/she cannot move anymore because of the fear, and will never return from the village. Since the beautiful statues are extraordinarily beautiful, if the sanity of a researcher is positive on going out of the village, the euphoria prevents him/her from leaving the village. The rest of the researchers, those who keep non-negative sanity and have the sanity of 0 on exiting the village, will return.

The investigation is over, regrettably with many missing persons. Now you have the list of returned researchers. Your task is to decide whether there exist any arrangements of beautiful and horrible statues not conflicting with the list, and, if any, show one of such arrangements.

The input consists of multiple datasets, each in the following format.

n m
A
B

n and m are the numbers of west-east and north-south streets, respectively. n and m are both positive even numbers at most 100. A and B are strings representing whether each researcher has returned from the village. A has the length n and B has the length m. Each string consists only of 0s and 1s. The i-th character of A represents whether the i-th of the first n researchers has returned from the village; 1 means the researcher has returned, and 0 means he/she has not. The j-th character of B represents whether the j-th of the remaining m researchers has returned from the village in the same manner.

The number of datasets does not exceed 100. The end of the input is indicated by a line containing two zeros.

For each dataset, if there exists no statue arrangement that does not contradict the list, output No in one line. Otherwise, output Yes in one line followed by n lines describing one of the possible arrangements. Each of the n lines should be a string of length m consisting only of `+'s and `−'s. A `+' being the j-th character of the i-th string means a beautiful statue on the intersection of the i-th street from the north and the j-th street from the west, while a `−' means a horrible statue.

Note that there may be multiple arrangements not contradicting the list. Any such output is judged as a correct output.

2 2
10
10
2 2
11
11
4 6
0010
100011
0 0

Yes
+-
-+
No
Yes
+---++
----++
+++---
---+--

The intelligence agency of the Kingdom uses a unique encryption method; a nonempty message consisting only of lowercase letters is encrypted into an expression <expr> complying with the grammar described by the following BNF.

<expr>	::=	<char> | <expr><expr> | ?(<expr>)
<char>	::=	a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

The original message before encryption is the string appearing first in the lexicographic order among the possible results of applying the procedure described below to the encrypted message.

Procedure: Repeat the following operation while ? remains in the expression.

1. Choose any occurrence of a contiguous substring of the form ?(s) (possibly the whole expression) such that s does not contain any symbols ?, (, or ).
2. If s is empty, simply remove the chosen occurrence of ?().
3. Otherwise, replace the chosen occurrence of ?(s) with the string obtained from s by deleting either the first or the last character.

For example, consider the expression ?(?(icp)c). Then, ?(icp) is the only occurrence that can be chosen, and this part is replaced with either cp or ic. Thus, the whole expression becomes either ?(cpc) or ?(icc). After that, by choosing the whole expressions and replace them, there are four possible results, pc, cp, cc, and ic. The original message is cc, which appears first in the lexicographic order among them.

You, an intelligence agent of the Republic, hostile to the Kingdom, have succeeded in obtaining an encrypted message, that is, an expression described above. Find the original message.

The input consists of multiple datasets. The first line of the input consists only of the number n of the datasets, where n does not exceed 50. The following n lines give the datasets, one in each line.

Each dataset is given in a single line consisting only of an expression <expr> complying with the grammar described by the BNF in the problem statement, and the expression consists of at most 1000 characters including symbols.

For each dataset, output in a line the string appearing first in the lexicographic order among the possible results of applying to it the procedure in the problem statement. It is guaranteed that the correct output is never an empty string.

6
?(icpc)
?(?(icpc))
?(ic)?(pc)
?(?(icp)c)
?(i?(?(c))pc)
?(bca)?(?(bca))

cpc
cp
cc
cc
ip
bca