A.Case of the Zeros and Ones

Andrewid the Android is a galaxy-famous detective. In his free time he likes to think about strings containing zeros and ones.

Once he thought about a string of length n consisting of zeroes and ones. Consider the following operation: we choose any two adjacent positions in the string, and if one them contains 0, and the other contains 1, then we are allowed to remove these two digits from the string, obtaining a string of length n - 2 as a result.

Now Andreid thinks about what is the minimum length of the string that can remain after applying the described operation several times (possibly, zero)? Help him to calculate this number.

Input

First line of the input contains a single integer n (1 ≤ n ≤ 2·10⁵), the length of the string that Andreid has.

The second line contains the string of length n consisting only from zeros and ones.

Output

Output the minimum length of the string that may remain after applying the described operations several times.

Sample test(s)

input

4
1100

output

0

input

5
01010

output

1

input

8
11101111

output

6

Note

In the first sample test it is possible to change the string like the following: .

In the second sample test it is possible to change the string like the following: .

In the third sample test it is possible to change the string like the following: .

 

题目类型：简单数学

算法分析：由题目可知，只要字符串中存在有’0’和’1’，就会发生”合并”进而将字符串的长度缩小，所以只要计算出字符串中’0’和’1’出现的最小次数，然后直接乘以2，再使用总长度减去即可

 

B.Case of Fake Numbers

Andrewid the Android is a galaxy-famous detective. He is now investigating a case of frauds who make fake copies of the famous Stolp's gears, puzzles that are as famous as the Rubik's cube once was.

Its most important components are a button and a line of n similar gears. Each gear has n teeth containing all numbers from 0 to n - 1 in the counter-clockwise order. When you push a button, the first gear rotates clockwise, then the second gear rotates counter-clockwise, the the third gear rotates clockwise an so on.

Besides, each gear has exactly one active tooth. When a gear turns, a new active tooth is the one following after the current active tooth according to the direction of the rotation. For example, if n = 5, and the active tooth is the one containing number 0, then clockwise rotation makes the tooth with number 1 active, or the counter-clockwise rotating makes the tooth number 4 active.

Andrewid remembers that the real puzzle has the following property: you can push the button multiple times in such a way that in the end the numbers on the active teeth of the gears from first to last form sequence 0, 1, 2, ..., n - 1. Write a program that determines whether the given puzzle is real or fake.

Input

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

The second line contains n digits a₁, a₂, ..., a_n (0 ≤ a_i ≤ n - 1) — the sequence of active teeth: the active tooth of thei-th gear contains number a_i.

Output

In a single line print "Yes" (without the quotes), if the given Stolp's gears puzzle is real, and "No" (without the quotes) otherwise.

Sample test(s)

input

3
1 0 0

output

Yes

input

5
4 2 1 4 3

output

Yes

input

4
0 2 3 1

output

No

Note

In the first sample test when you push the button for the first time, the sequence of active teeth will be 2 2 1, when you push it for the second time, you get 0 1 2.

 

题目类型：暴力枚举

算法分析：直接按照题目的要求模拟10000次，然后判断是否满足条件即可

 

C.Case of Matryoshkas

Andrewid the Android is a galaxy-famous detective. He is now investigating the case of vandalism at the exhibition of contemporary art.

The main exhibit is a construction of n matryoshka dolls that can be nested one into another. The matryoshka dolls are numbered from 1 to n. A matryoshka with a smaller number can be nested in a matryoshka with a higher number, two matryoshkas can not be directly nested in the same doll, but there may be chain nestings, for example,1 → 2 → 4 → 5.

In one second, you can perform one of the two following operations:

• Having a matryoshka athat isn't nested in any other matryoshka and a matryoshka b, such that b doesn't contain any other matryoshka and is not nested in any other matryoshka, you may put a in b;
• Having a matryoshka adirectly contained in matryoshka b, such that b is not nested in any other matryoshka, you may get a out of b.

According to the modern aesthetic norms the matryoshka dolls on display were assembled in a specific configuration, i.e. as several separate chains of nested matryoshkas, but the criminal, following the mysterious plan, took out all the dolls and assembled them into a single large chain (1 → 2 → ... → n). In order to continue the investigation Andrewid needs to know in what minimum time it is possible to perform this action.

Input

The first line contains integers n (1 ≤ n ≤ 10⁵) and k (1 ≤ k ≤ 10⁵) — the number of matryoshkas and matryoshka chains in the initial configuration.

The next k lines contain the descriptions of the chains: the i-th line first contains number m_i (1 ≤ m_i ≤ n), and thenm_i numbers a_i1, a_i2, ..., a_imi — the numbers of matryoshkas in the chain (matryoshka a_i1 is nested into matryoshkaa_i2, that is nested into matryoshka a_i3, and so on till the matryoshka a_imi that isn't nested into any other matryoshka).

It is guaranteed that m₁ + m₂ + ... + m_k = n, the numbers of matryoshkas in all the chains are distinct, in each chain the numbers of matryoshkas follow in the ascending order.

Output

In the single line print the minimum number of seconds needed to assemble one large chain from the initial configuration.

Sample test(s)

input

3 2
2 1 2
1 3

output

1

input

7 3
3 1 3 7
2 2 5
2 4 6

output

10

Note

In the first sample test there are two chains: 1 → 2 and 3. In one second you can nest the first chain into the second one and get 1 → 2 → 3.

In the second sample test you need to disassemble all the three chains into individual matryoshkas in 2 + 1 + 1 = 4 seconds and then assemble one big chain in 6 seconds.

 

题目类型：贪心+枚举

算法分析：贪心策略是找到一个从1开始每个元素之间相差1的最长递增数列a，即这个数列标号的娃娃不拆出来，然后其他的娃娃如果在某一个娃娃中，则将其取出；最后将每一个a之后的娃娃一个一个地套入即可

 

A.Kyoya and Photobooks

Kyoya Ootori is selling photobooks of the Ouran High School Host Club. He has 26 photos, labeled "a" to "z", and he has compiled them into a photo booklet with some photos in some order (possibly with some photos being duplicated). A photo booklet can be described as a string of lowercase letters, consisting of the photos in the booklet in order. He now wants to sell some "special edition" photobooks, each with one extra photo inserted anywhere in the book. He wants to make as many distinct photobooks as possible, so he can make more money. He asks Haruhi, how many distinct photobooks can he make by inserting one extra photo into the photobook he already has?

Please help Haruhi solve this problem.

Input

The first line of input will be a single string s (1 ≤ |s| ≤ 20). String s consists only of lowercase English letters.

Output

Output a single integer equal to the number of distinct photobooks Kyoya Ootori can make.

Sample test(s)

input

a

output

51

input

hi

output

76

Note

In the first case, we can make 'ab','ac',...,'az','ba','ca',...,'za', and 'aa', producing a total of 51 distinct photo booklets.

 

题目类型：简单模拟

算法分析：直接推出规律计算即可

 

B.Ohana Cleans Up

Ohana Matsumae is trying to clean a room, which is divided up into an n by n grid of squares. Each square is initially either clean or dirty. Ohana can sweep her broom over columns of the grid. Her broom is very strange: if she sweeps over a clean square, it will become dirty, and if she sweeps over a dirty square, it will become clean. She wants to sweep some columns of the room to maximize the number of rows that are completely clean. It is not allowed to sweep over the part of the column, Ohana can only sweep the whole column.

Return the maximum number of rows that she can make completely clean.

Input

The first line of input will be a single integer n (1 ≤ n ≤ 100).

The next n lines will describe the state of the room. The i-th line will contain a binary string with n characters denoting the state of the i-th row of the room. The j-th character on this line is '1' if the j-th square in the i-th row is clean, and '0' if it is dirty.

Output

The output should be a single line containing an integer equal to a maximum possible number of rows that are completely clean.

Sample test(s)

input

4
0101
1000
1111
0101

output

2

input

3
111
111
111

output

3

Note

In the first sample, Ohana can sweep the 1st and 3rd columns. This will make the 1st and 4th row be completely clean.

In the second sample, everything is already clean, so Ohana doesn't need to do anything.

 

题目类型：简单模拟

算法分析：首先计算一下原来有多少行是都是1，记为maxval。根据题目的要求可知，只有两个完全相同的行才可以通过列变换来同步变成都是1的形式。所以只要找到行相同的最大值，然后与原来有多少1比较即可

 

C.Kyoya and Colored Balls

Kyoya Ootori has a bag with n colored balls that are colored with k different colors. The colors are labeled from 1 tok. Balls of the same color are indistinguishable. He draws balls from the bag one by one until the bag is empty. He noticed that he drew the last ball of color i before drawing the last ball of color i + 1 for all i from 1 to k - 1. Now he wonders how many different ways this can happen.

Input

The first line of input will have one integer k (1 ≤ k ≤ 1000) the number of colors.

Then, k lines will follow. The i-th line will contain c_i, the number of balls of the i-th color (1 ≤ c_i ≤ 1000).

The total number of balls doesn't exceed 1000.

Output

A single integer, the number of ways that Kyoya can draw the balls from the bag as described in the statement, modulo 1 000 000 007.

Sample test(s)

input

3
2
2
1

output

3

input

4
1
2
3
4

output

1680

Note

In the first sample, we have 2 balls of color 1, 2 balls of color 2, and 1 ball of color 3. The three ways for Kyoya are:
1 2 1 2 3
1 1 2 2 3
2 1 1 2 3

 

题目类型：组合+DP

算法分析：使用res表示取前i种颜色时的方案数，则i = 1时，res = 1;然后递推方程为res = res * Com (sum + cnt[i] – 1, cnt[i] – 1) % MOD，其中sum表示小于i的所有的颜色的球的个数(前缀和)，注意使用组合数取模！！！！！！！

 

 

A.Vanya and Table

Vanya has a table consisting of 100 rows, each row contains 100 cells. The rows are numbered by integers from 1to 100 from bottom to top, the columns are numbered from 1 to 100 from left to right.

In this table, Vanya chose n rectangles with sides that go along borders of squares (some rectangles probably occur multiple times). After that for each cell of the table he counted the number of rectangles it belongs to and wrote this number into it. Now he wants to find the sum of values in all cells of the table and as the table is too large, he asks you to help him find the result.

Input

The first line contains integer n (1 ≤ n ≤ 100) — the number of rectangles.

Each of the following n lines contains four integers x₁, y₁, x₂, y₂ (1 ≤ x₁ ≤ x₂ ≤ 100, 1 ≤ y₁ ≤ y₂ ≤ 100), where x₁and y₁ are the number of the column and row of the lower left cell and x₂ and y₂ are the number of the column and row of the upper right cell of a rectangle.

Output

In a single line print the sum of all values in the cells of the table.

Sample test(s)

input

2
1 1 2 3
2 2 3 3

output

10

input

2
1 1 3 3
1 1 3 3

output

18

Note

Note to the first sample test:

Values of the table in the first three rows and columns will be as follows:

121

121

110

So, the sum of values will be equal to 10.

Note to the second sample test:

Values of the table in the first three rows and columns will be as follows:

222

222

222

So, the sum of values will be equal to 18.

 

题目类型：简单模拟

算法分析：由于n比较小，所以直接使用O(n^3)的暴力模拟可以过掉，将每个位置自加1后，统计最后所有数的和即可，当然最好的方法是直接算出每一次要加的值，时间复杂度是O(n)的

 

B.Vanya and Books

Vanya got an important task — he should enumerate books in the library and label each book with its number. Each of the n books should be assigned with a number from 1 to n. Naturally, distinct books should be assigned distinct numbers.

Vanya wants to know how many digits he will have to write down as he labels the books.

Input

The first line contains integer n (1 ≤ n ≤ 10⁹) — the number of books in the library.

Output

Print the number of digits needed to number all the books.

Sample test(s)

input

13

output

17

input

4

output

4

Note

Note to the first test. The books get numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, which totals to 17 digits.

Note to the second sample. The books get numbers 1, 2, 3, 4, which totals to 4 digits.

 

题目类型：简单模拟

算法分析：首先得到所求数n的位数，然后考虑到1~9中有9个数字，10~99中有90*2个数字，以此类推。直接先求出小于n的整范围的值，最后再加上当前位数的数字个数和

 

C.Vanya and Scales

Vanya has a scales for weighing loads and weights of masses w⁰, w¹, w², ..., w¹⁰⁰ grams where w is some integer not less than 2 (exactly one weight of each nominal value). Vanya wonders whether he can weight an item with massm using the given weights, if the weights can be put on both pans of the scales. Formally speaking, your task is to determine whether it is possible to place an item of mass m and some weights on the left pan of the scales, and some weights on the right pan of the scales so that the pans of the scales were in balance.

Input

The first line contains two integers w, m (2 ≤ w ≤ 10⁹, 1 ≤ m ≤ 10⁹) — the number defining the masses of the weights and the mass of the item.

Output

Print word 'YES' if the item can be weighted and 'NO' if it cannot.

Sample test(s)

input

3 7

output

YES

input

100 99

output

YES

input

100 50

output

NO

Note

Note to the first sample test. One pan can have an item of mass 7 and a weight of mass 3, and the second pan can have two weights of masses 9 and 1, correspondingly. Then 7 + 3 = 9 + 1.

Note to the second sample test. One pan of the scales can have an item of mass 99 and the weight of mass 1, and the second pan can have the weight of mass 100.

Note to the third sample test. It is impossible to measure the weight of the item in the manner described in the input.

 

题目类型：进制转换

算法分析：本题要求的是是否存在m = A0 * w^0 + A1 * w^1 + A2 * w^2 + …… A100 * w^100。其中Ai只能取值0、1和w - 1(因为题目中说砝码最多用一个)，取其他的值是无解的。其中Ai = 0表示w^i这种砝码不取，Ai = 1表示w^i这种砝码取，而Ai = w - 1表示在待称重物品一侧放置砝码w^i。解释最后这种情况，由于有Ai * w^i = (w - 1) * w^i = w^(i+1) – w^i。方程左边减去一个w^i等价于右边加上一个w^i。由分析可知，可以使用进制转换的思想从低位到高位判断位上的数字。由于转换时方程左右要同时不断地除以w。如果有m = 1 * w^0 + 0 * w^1 + (w-1) * w^2 + …… 1 * w^100。则m / w ^ 2 = w - 1 + …… 1 * w^100，此时要在方程的左边加上一个1，切记！！！！！！本题还可以使用贪心的方法，就是每次先拿最大砝码去称，直到称完或者还留下一些没有称完(无解)

 

D.Vanya and Triangles

Vanya got bored and he painted n distinct points on the plane. After that he connected all the points pairwise and saw that as a result many triangles were formed with vertices in the painted points. He asks you to count the number of the formed triangles with the non-zero area.

Input

The first line contains integer n (1 ≤ n ≤ 2000) — the number of the points painted on the plane.

Next n lines contain two integers each x_i, y_i ( - 100 ≤ x_i, y_i ≤ 100) — the coordinates of the i-th point. It is guaranteed that no two given points coincide.

Output

In the first line print an integer — the number of triangles with the non-zero area among the painted points.

Sample test(s)

input

4
0 0
1 1
2 0
2 2

output

3

input

3
0 0
1 1
2 0

output

1

input

1
1 1

output

0

Note

Note to the first sample test. There are 3 triangles formed: (0, 0) - (1, 1) - (2, 0); (0, 0) - (2, 2) - (2, 0);(1, 1) - (2, 2) - (2, 0).

Note to the second sample test. There is 1 triangle formed: (0, 0) - (1, 1) - (2, 0).

Note to the third sample test. A single point doesn't form a single triangle.

 

题目类型：斜率分块+组合

算法分析：用总的方案数减去不满足条件的方案数即可，其中总的方案数为C(n, 3)，不满足条件的方案数是那些共线点所组成的方案。所以可以先按照标号枚举每一个点，然后计算该点和其它点(标号比它大的点)之间的斜率，最后对计算出来的斜率进行排序，判断共线点的个数temp，然后累加C(temp, 2)到sum上。最后直接输出C(n, 3) - sum即可。时间复杂度是O(n(n + nlog(n)+n))

 

E.Vanya and Brackets

Vanya is doing his maths homework. He has an expression of form , where x₁, x₂, ..., x_nare digits from 1 to 9, and sign  represents either a plus '+' or the multiplication sign '*'. Vanya needs to add onepair of brackets in this expression so that to maximize the value of the resulting expression.

Input

The first line contains expression s (1 ≤ |s| ≤ 5001, |s| is odd), its odd positions only contain digits from 1 to 9, and even positions only contain signs  +  and  * .

The number of signs  *  doesn't exceed 15.

Output

In the first line print the maximum possible value of an expression.

Sample test(s)

input

3+5*7+8*4

output

303

input

2+3*5

output

25

input

3*4*5

output

60

Note

Note to the first sample test. 3 + 5 * (7 + 8) * 4 = 303.

Note to the second sample test. (2 + 3) * 5 = 25.

Note to the third sample test. (3 * 4) * 5 = 60 (also many other variants are valid, for instance, (3) * 4 * 5 = 60).

 

题目类型：贪心+表达式计算

算法分析：本题一个显然的贪心策略是：左括号的左边第一个符号是'*'或者没有，右括号的右边第一个符号是'*'或者没有。因为表达式中只有'+'和'*'，且'+'的优先级比'*'要低，两个数先相加再相乘要比先相乘再相加的结果大。所以如果不是'*'的话，总可以再向两边扩展，直到满足条件。按照分析可知，可以直接枚举乘号的位置，然会计算表达式的值，取其中最大的即可