写在前面

第一次参加省赛，感觉十分奇妙。感谢两位队友的强力大腿能让我安心躺银。吐槽中大的云桌面，把同学们都整蒙了。中午的麦当当还算可以，衣服不错，下次还来。

版权说明

文章所提供的题面仅供学习交流使用，严禁任何牟利行为，如有侵权请联系Wonyeaweat@foxmail.com，我们将会第一时间配合工作。

A.Chessboard

Problem Description

There are N chess pieces on a huge chessboard of 10^9 * 10^9 (the rows are numbered from 1 to 10^9 from top to bottom and the columns are numbered from 1 to 10^9 from left to right. All pieces are located in different gids. and the i-th piece is in the yi-th column of the xi-th row. All pieces have their own values. and the value of the i-th piece is excatly i.

Your task is to take the chess pieces and maximize the sum of values of the pieces you take. But there are M conditions of the following two types that should be met:

"R i k" there is a dividing line between the (i-1)-th row and the i-th row, and you can take up to k from the pieces under the line;
"C i k" there is a dividing line between the (i-1)-th column and the i-th column, and you can take up to k from the pieces on the right of the line.

Input

The first line contains integer N(i<=N<=500), denotes the number of chess pieces.
For the next N lines, the i-th line contains two integers xi and yi,denotes the position of the i-th piece whose value is also i.
The (N+2) - th line contains integer M(i<=M<=10^5) ,denotes the number of conditions.
Then M lines follow , describing conitions in the format given in the statement.

Output

Print the maximak sum of values of the chess pieces you take.

Sample Input

4
1 2
2 2
3 1
3 2
4
R 2 3
C 1 4
R 3 1
C 2 2

Sample Output

Hints

You can take the first three pieces (or thake the second piece and the fourth piece).

B,Bulid Tree

Description

You need to conduct an n-ary tree with m layers.all the edges in this tree have a weight. But this weight cannot be chosen arbitratily you can only choose from set S, the size of set S is k,each element in the set can only be used once.Node 0 is the root of tree.
We use d(i) for the distance from root to node i.Out goal is to minimize the following expression:
$min \sum_{i=0}^{N}{d(i)}$
Please find the minimum value of this expression and output it.Because it may be a big number, you should output the answer mod P.

Input

The input file contains 2 lines.
The first line contains 4 integers, these respectively is k,m,n,p.(2<=k<=200000,2<=p<=10^15)
The second line contains k integers,represent the set S, the elements in the set guarantee less than or equal to 10^15.
We guarantee that k is greater than or equal to the number of edges.

Output

The output file contains an integer, represent the answer.

Sample Input

5 2 3 10
1 2 3 4 5

Sample Output

C.Chika and Friendly Pairs

Problem Description

Chika gives you an integer sequence a1,a2,...,an, and m tasks. For each task , you need to answer the number of "friendly pairs" in a given interval.

friendly pair: for two integers ai and aj, if i<j and the absolute value of ai-aj is no more than a given constant integer K. then (i,j) is called a "friendly pair". A friendly pair (i, j) in a interval [L, R] should satisfy L<=i<=j<=R.

Input

The first line contains 3 integers n (1<=n<=27000) , m(1<=m<=27000) and K(1<=K<=10^9) ,representing the number of integers in the sequence a, the number if tasks and the given constant integer.
The second line contains n integers.representing the integers in the sequence a, Every integer of sequence a is no more than 10^9.
Then m lines follow, each of which contains two integers L, R,(1<=L<=R<=n). The meaning is to ask the number of "friendly pairs" in the interval [L,R].

Output

For each task, you need to print one line, including only one integer, representing the number of "friendly pairs" int the query interval.

Sample Input

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

Sample Output

0
2
1
3
1

D-Chika and Solid Geometry

Problem Description

Chika has just learned about solid geometry! She is very interested in the volume of three-dimensional geometric shapes. so she decides to test you.Before that, she is going to tell you definitions of the following two three-dimensional geometric shapes.

Oblique circular cone: A cone whose surface is generated by lines joining a fixed point called the apex to the points of a circle, the fixed point lying on a line that is not prependicular to the circle at its centre.(The circular cone is a special kind of oblique circular cone.)

Pyramid:A polyhedron formed by connecting a polygonal base and a point, called the apex. Each base edge and apex from a triangle, called a lateral face. It is a conic solid with polygonal base.A pyramid with an n-sided base has n+1 verticles, n+1 faces and 2n edges.

Chika gives you an oblique circular cone and a pyramid placed in the space rectangular coordinate system. Their bottoms are on the plane z = 0.The z-coordinates of their apexes are bigger than 0.some parts of them may overlap with each other. You need to help Chika to calculate the volume of the union of the two three-dimensional geometric shapes.

Input

The input file contains several lines.
The first line contains three integers x,y,z (z>0) , which are the coordinates of the apex of the oblique circular cone.
The second row contains three integers x, y, and r(r>0) . x and y are the x-coordinate and the y-coordinate of the center of the oblique circular cone's bottom circle.r is radius of the oblique circular cones's bottom circle.
The third line contains three integers x, y, and z(z>0) ,which are the coordinates of the apex of the pyramid.
The fourth line contains a positive integer n(n<=1000) ,which is the number of verticles of the pyramid's bottom polygon,
Then n lines follow. each line contains two integers x, y, which are the x-coordinate and y-coordinate of the n verticles of the pyramid's bottom polygon. Vertex coordinates are given in counterclockwise order.These points do not coincide. It is guaranteed that the absolute values of all input integers are not greater than 1000.

output

The output file should contain only one line, including one real number, representing the volume of the union of the oblique circular cone and the pyramid. the relative error or absolute error between your answer and the standard answer should be less than 10^-6.

Sample Input

0 0 2
2 0 2
0 0 2
3
2 0
4 -2
4 2

Sample Output

8.9498519738

E.Hello GDCPC

Problem Description

You have a string of lowercase letters. You need to find as many as sequence "gdCpc" as possible. But letters in the same position can only be used once.

Input

The input file contains two lines,
The first line is an integer n show the length of string.(1<=n<=2*10^5)
the second line is a string of length n consisting of lowercase letters and uppercase letters.

Output

The output file contains an integer show the maximum number of different subsequences found.

Sample Input

10
gdCgdCpcpc

Sample output

F.Neko and function

Problem Description

Neko learnt a new function f(n, k) today.f(n, k) is the number of way to select k numbers ai,(ai>1), $\prod_{i=1}^{k} ai =n$ .
Neko thinks this function is too easy, so she want to know $\sum_{i=1}^{n} f(i, k)$ , Calculate the sum after mod 10^9+7,
Note that if n=6, $6=2*3$ , $6=3*2$ are different way.

Input

Input one line contains two integers n,k (1,=n<=2^30 , 1<=k<=30)

Output

Output the number of way for selecting nodes.

Sample Input

10 2

Sample output

G.Neko and quadrilateral

Problem Description

Neko have k poits on a 2-dimensional plane. And no three points are in a straight line, Now Neko want you to select four different points to form a quadrilateral .Neko want to show the max area and the min area from these quadrilateral.

Input

The first line contains one integer n(1<=n<=2000)
The next n lines, each line contains two integers x,y(-10^9 <=x,y<=10^9 ),means the coordinates of the i-th point.

Output

Output the min area and the max area in one line,For convenience , please output twice the area,

Sample Input

6
1 1
2 2
1 3
4 1
0 -2
3 5

Sample Output

3 27

H.Neko and sequence

Problem Description

One day, Inu asked Neko a question: GIve you a sequence with n elements, the index for the first element is 0, the last is n-1.They are arranged in rings. 0 and n-1 are next to each other.The i-th element has a character s[i] which is '(' or ')'. Let f(i,d) means the last place to arrive by starting with i and taking d steps, If you are in i-th element now and s[i]='(' , you will arrive (i-k+n)%n -th element in next step, or you will arrive (i+k) %n -th element .And there are q questions, Each question has three integers l,r,d You have to calculate $\sum_{i=l}^{r} f(i,d)$ .

Input

The first line contains three integers n,q,k (1<=n,q<=10^5, 1<=k<=n) . the second line contains a sequence, the i-th element means s[i], The next q line , each line contains three integers l,r,d(0<=l<=r<n,1<=d<=10^9)

Output

For each question output the sum in one line.

Sample Input

6 5 1
())()(
0 1 3
1 3 2
1 4 3
2 5 6
0 3 4

Sample Output

7
8
12
14
12

I.Neko and tree

Problem Description

Neko has a tree with n nodes.There are m key nodes on tree.Neko want you to select some key nodes satisying the distance between any two selected nodes less than or equal to k.Neko thinks this work is too easy, so Neko want to know how many different ways for selecting nodes, Calculate the answer after mod 10^9+7,Note that you have to select at least one key node.

Input

The first line contains three integers n,m,k(1<=n,m,k<=5000) The next n-1 line, each line contains 2 integers u,v, indicating there is an edge connecting node u and node v.The last line contains m integers, indicating key node.

Output

Output the number of way for selecting nodes.

Sample Input

4 3 2
1 2
1 3
2 4
2 3 1

Sample Output

J.Neko and triangle

Problem Description

Neko haves a sequence with n points, the i-th point Ai, And she gets m key points, Define the origin point is O=(0,0). For each key point Pk, you need to find a interval [l,r], to make $\sum_{i=l}^{r} Si$ max.Si is the directed area of triangle OPkAi, There may be a lot of intervals suitable, so you only need output the sum of area.

Input

The first line contains two integers n,m(1<=n,m<=10^5) The next n lines ,each line contains two integers x,y,(0<=x,y<=10^5),means the coordinate of the i-th point Ai. The next m lines, each line cotains two integers x, y(0<=x,y<=10^5) means the coordinate of the i-th key point Pi.

Output

For each key point, output the maxarea in one line, For convenience please output twice the area.

Sample Input

4 4
1 3
2 4
3 2
4 3
1 1
2 2
3 3
4 4

Sample Output

4
8
12
16

K.SSY and JLBD

Problem Description

Mahjong is a board game with a long history, But Mahjong has different rules in different city. A deck of mahjong consists of 136 cards. It contains 1-9 card in three suits, and seven kinds of word card(dong,nan,xi,bei,zhong,fa,bai) there are 4 same cards for each kind of card in a deck of mahjong. In a mysterious country, the rules of mahjong are very simple. In the game, each player has 14 card, There are only two ways people can win the game.

shisanyao : You should hace all 1 and 9 card in three suits and seven kinds of word card at the same time, and an extra card with any kind of 1 and 9 or word.
jiulianbaodeng: Firstly, You should make sure that you have the same suit in your hand. Secondly, for card "1" and card "9", you should have at least Three. But for card "2" to "8", at least one, For example , both "11112345678999" and "11122345678999" can win the game.
Now you know a player's 14 cards. Please judge which card type he can used to win the game.

Input

The input file contains 14 lines, Each line has a string representing a card.
For three suits of card "1" to "9", We use two characters for the type. the first character is a number 1 to 9, and the second character represent the suit.('s','p','w').
For the word cards, as shown in the description, we use full spelling pinyin representing them.

Output

If player's card meet the "shisanyao" condition , you should output "shisanyao!".
If player's card meet the "jiulianbaodeng" condition, you should output "jiulianbaodeng!".
Otherwise you should output "I dont know!".

Sample Input

1w
5w
2w
6w
5w
9w
9w
7w
1w
3w
9w
4w
1w
8w

Sample Output

jiulianbaodeng!

L.Can you raed it croretcly?

Problem Description

Do you feel weird when reading the problem title? You can understand word meanning correctly even if its spelling is wrong,According to research if the initial and last letter of the word are right, and just swap the others, human can correct the soelling of the word automatically. Now , giving you a word and its correct spelling , can you correct it automatically?

input

The input contains several test cases.Each test case consist of one line with two strings, each string only contains lowercase letter, and its length is no more than 20.

Output

Output "Equal" when the two strings are same ; output "Yes" when you can correct it ,otherwise output "No".

Sample Input

raed read
it it
croretcly correctly
raed dear

Sample Output

Yes
Equal
Yes
No

GDCPC-2019 暨“中智杯”第17届广东大学生程序设计竞赛

写在前面

版权说明

A.Chessboard

Problem Description

Input

Output

Sample Input

Sample Output

Hints

B,Bulid Tree

Description

Input

Output

Sample Input

Sample Output

C.Chika and Friendly Pairs

Problem Description

Input

Output

Sample Input

Sample Output

D-Chika and Solid Geometry

Problem Description

Input

output

Sample Input

Sample Output

E.Hello GDCPC

Problem Description

Input

Output

Sample Input

Sample output

F.Neko and function

Problem Description

Input

Output

Sample Input

Sample output

G.Neko and quadrilateral

Problem Description

Input

Output

Sample Input

Sample Output

H.Neko and sequence

Problem Description

Input

Output

Sample Input

Sample Output

I.Neko and tree

Problem Description

Input

Output

Sample Input

Sample Output

J.Neko and triangle

Problem Description

Input

Output

Sample Input

Sample Output

K.SSY and JLBD

Problem Description

Input

Output

Sample Input

Sample Output

L.Can you raed it croretcly?

Problem Description

input

Output

Sample Input

Sample Output