Problem Statement

Summer vacation ended at last and the second semester has begun. You, a Kyoto University student, came to university and heard a rumor that somebody will barricade the entrance of your classroom. The barricade will be built just before the start of the A-th class and removed by Kyoto University students just before the start of the B-th class. All the classes conducted when the barricade is blocking the entrance will be cancelled and you will not be able to attend them. Today you take N classes and class i is conducted in the t_i-th period. You take at most one class in each period. Find the number of classes you can attend.

Constraints

• 1 \leq N \leq 1000
• 1 \leq A < B \leq 10^9
• 1 \leq t_i \leq 10^9
• All t_i values are distinct.

Sample Input 1

5 5 9
4
3
6
9
1

Sample Output 1

4

You can not only attend the third class.

Sample Input 2

5 4 9
5
6
7
8
9

Sample Output 2

1

You can only attend the fifth class.

Sample Input 3

4 3 6
9
6
8
1

Sample Output 3

4

You can attend all the classes.

Sample Input 4

2 1 2
1
2

Sample Output 4

1

You can not attend the first class, but can attend the second.

Problem Statement

Kyoto University Programming Contest is a programming contest voluntarily held by some Kyoto University students. This contest is abbreviated as Kyoto University Programming Contest and called KUPC.

source: Kyoto University Programming Contest Information

The problem-preparing committee met to hold this year's KUPC and N problems were proposed there. The problems are numbered from 1 to N and the name of i-th problem is P_i. However, since they proposed too many problems, they decided to divide them into some sets for several contests.

They decided to divide this year's KUPC into several KUPCs by dividing problems under the following conditions.

• One KUPC provides K problems.
• Each problem appears at most once among all the KUPCs.
• All the first letters of the problem names in one KUPC must be different.

You, one of the committee members, want to hold as many KUPCs as possible. Write a program to find the maximum number of KUPCs that can be held this year.

Constraints

• 1 \leq N \leq 10^4
• 1 \leq K \leq 26
• 1 \leq |P_i| \leq 10
• All characters in P_i are capital letters.

Note that, for each i and j (1 \leq i < j \leq N), P_i \neq P_j are not necessarily satisfied.

Sample Input 1

9 3
APPLE
ANT
ATCODER
BLOCK
BULL
BOSS
CAT
DOG
EGG

For example, three KUPCs can be held by dividing the problems as follows.

• First: APPLE, BLOCK, CAT
• Second: ANT, BULL, DOG
• Third: ATCODER, BOSS, EGG

Sample Output 1

3

Sample Input 2

3 2
KU
KYOUDAI
KYOTOUNIV

Sample Output 2

0

No KUPC can be held.

Problem Statement

A professor invented Cookie Breeding Machine for his students who like cookies very much.

When one cookie with the taste of x is put into the machine and a non-negative integer y less than or equal to 127 is input on the machine, it consumes the cookie and generates two cookies with the taste of y and (x XOR y).

Here, XOR represents Bitwise Exclusive OR.

At first, there is only one cookie and the taste of it is D .

Find the maximum value of the sum of the taste of the exactly N cookies generated after the following operation is conducted N-1 times.

1. Put one of the cookies into the machine.
2. Input a non-negative integer less than or equal to 127 on the machine.

Constraints

• 1 \leq T \leq 1000
• 1 \leq N_t \leq 1000 (1 \leq t \leq T)
• 1 \leq D_t \leq 127 (1 \leq t \leq T)

Sample Input 1

3
3 1
4 108
1 10

Sample Output 1

255
400
10

On the 1st test case, if the machine is used as follows, three cookies with the taste of 61, 95 and 99 are generated. Since the sum of these values is maximum among all possible ways, the answer is 255.

1. Put the cookie with the taste of 1 and input an integer 60 on the machine, lose the cookie and get two cookies with the taste of 60 and 61.
2. Put the cookie with the taste of 60 and input an integer 99 on the machine, lose the cookie and get two cookies with the taste of 99 and 95.

On the 3rd test case, the machine may not be used.

Problem Statement

There is a long blackboard with 2 rows and N columns in a classroom of Kyoto University. This blackboard is so long that it is impossible to tell which cells are already used and which unused.

Recently, a blackboard retrieval device was installed at the classroom. To use this device, you type a search query that forms a rectangle with 2 rows and any length of columns, where each cell is used or unused. When you input a query, the decive answers whether the rectangle that corresponds to the query exists in the blackboard. Here, for a rectangle that corresponds to a search query, if two integer i, j ( i < j ) exist and the rectangle equals to the partial blackboard between column i and j , the rectangle is called a sub-blackboard of the blackboard.

You are currently preparing for a presentation at this classroom. To make the presentation go well, you decided to write a program to detect the status of the whole blackboard using the retrieval device. Since it takes time to use the device, you want to use it as few times as possible.

The status of the whole blackboard is already determined at the beginning and does not change while you are using the device.

Query Limit

The maximun number of search queries is 420. If the number of queries exceeds the limit, the result will be Query Limit Exceeded .

Sample Input and Output

The following is an example where N=3 and the blackboard is as follows.

.#.
...

Note that your program does not know the state of the blackboard.

  

    
Output of your program
    
Input to your program
    
Explanation
  
  

    

    
3
    
The length of the blackboard is given
  
  

    
..
##
    

    
Output a search query
  
  

    

    
F
    
The sub-blackboard does not exist
  
  

    
.
.
    

    
Output a search query
  
  

    

    
T
    
The sub-blackboard exists
  
  

    
..
..
    

    
Output a search query
  
  

    

    
F
    
The sub-blackboard does not exist
  
  

    
.#
..
    

    
Output a search query
  
  

    

    
T
    
The sub-blackboard exists
  
  

    
.#.
...
    

    
Output a search query
  
  

    

    
end
    
Exit your program because the above sub-blackboard equals to the whole blackboard. 
  

Problem Statement

There are some goats on a grid with H rows and W columns. Alice wants to put some fences at some cells where goats do not exist so that no goat can get outside the grid. Goats can move in the four directions, that is, up, down, right and left. Goats can not move onto the cells where fences are placed. If a goat exists at one of the outermost cells in the grid, it can move outside. Goats do not move until all fences are placed. Find the minimum number of fences to be placed.

Constraints

• 1 \leq H \leq 100
• 1 \leq W \leq 100
• There is at least one goat on the given grid.

Sample Input 1

4 5
.....
.....
..X..
.....

Sample Output 1

4

The optimum answer is to put fences at the cells located at row 3 and column 2, row 2 and column 3, row 3 and column 4, and row 4 and column 3.

Sample Input 2

2 2
..
.X

Sample Output 2

-1

In this case, there is no way to keep the goats inside the grid.

Sample Input 3

6 6
......
......
..X...
.X..X.
..X...
......

Sample Output 3

10

Problem Statement

You are going to take the entrance examination of Kyoto University tomorrow and have decided to memorize a set of strings S that is expected to appear in the examination. Since it is really tough to memorize S as it is, you have decided to memorize a single string T that efficiently contains all the strings in S.

• Every string in S is a consecutive subsequence⁽¹⁾ in T .
• For every pair of strings x, y (x \neq y) in S , x is not a subsequence⁽²⁾ of y.

Note that (1) is ''consecutive subsequence'', while (2) is ''subsequence''.

The next day, you opened the problem booklet at the examination and found that you can get a full score only if you remember S. However, You have forgot how to reconstruct S from T . Since all you remember is that T satisfies the above conditions, first you have decided to find the maximum possible number of elements in S .

Constraints

• 1 \leq |T| \leq 10^5
• T consists of only lowercase letters.

Partial points

• 30 points will be awarded for passing the test set satisfying the condition: 1 \leq |T| \leq 50 .
• Another 30 points will be awarded for passing the test set satisfying the condition: 1 \leq |T| \leq 10^3.

Sample Input 1

abcabc

Sample Output 1

3

Sample Input 2

abracadabra

Sample Output 2

7

Sample Input 3

abcbabbcabbc

Sample Output 3

8

Sample Input 4

bbcacbcbcabbabacccbbcacbaaababbacabaaccbccabcaabba

Sample Output 4

44

Problem Statement

Kyoto University decided to build a straight wall on the west side of the university to protect against gorillas that attack the university from the west every night. Since it is difficult to protect the university at some points along the wall where gorillas attack violently, reinforcement materials are also built at those points. Although the number of the materials is limited, the state-of-the-art technology can make a prediction about the points where gorillas will attack next and the number of gorillas that will attack at each point. The materials are moved along the wall everyday according to the prediction. You, a smart student majoring in computer science, are called to find the way to move the materials more efficiently.

Theare are N points where reinforcement materials can be build along the straight wall. They are numbered 1 through N. Because of the protection against the last attack of gorillas, A_i materials are build at point i (1 \leq i \leq N). For the next attack, the materials need to be rearranged such that at least B_i materials are built at point i (1 \leq i \leq N). It costs |i - j| to move 1 material from point i to point j. Find the minimum total cost required to satisfy the condition by moving materials. You do not need to consider the attack after the next.

Constraints

• 1 \leq N \leq 10^5
• A_i \geq 1
• B_i \geq 1
• A_1 + A_2 + ... + A_N \leq 10^{12}
• B_1 + B_2 + ... + B_N \leq A_1 + A_2 + ... + A_N
• There is at least one way to satisfy the condition.

Sample Input 1

2
1 5
3 1

Sample Output 1

2

It costs least to move 2 materials from point 2 to point 1.

Sample Input 2

5
1 2 3 4 5
3 3 1 1 1

Sample Output 2

6

Sample Input 3

27
46 3 4 2 10 2 5 2 6 7 20 13 9 49 3 8 4 3 19 9 3 5 4 13 9 5 7
10 2 5 6 2 6 3 2 2 5 3 11 13 2 2 7 7 3 9 5 13 4 17 2 2 2 4

Sample Output 3

48

The input of this test case satisfies both the first and second additional constraints.

Sample Input 4

18
3878348 423911 8031742 1035156 24256 10344593 19379 3867285 4481365 1475384 1959412 1383457 164869 4633165 6674637 9732852 10459147 2810788
1236501 770807 4003004 131688 1965412 266841 3980782 565060 816313 192940 541896 250801 217586 3806049 1220252 1161079 31168 2008961

Sample Output 4

6302172

The input of this test case satisfies the second additional constraint.

Sample Input 5

2
1 99999999999
1234567891 1

Sample Output 5

1234567890

The input and output values may exceed the range of 32-bit integer.

Problem Statement

Eli- 1 started a part-time job handing out leaflets for N seconds. Eli- 1 wants to hand out as many leaflets as possible with her special ability, Cloning. Eli- gen can perform two kinds of actions below.

• Clone herself and generate Eli- (gen + 1) . (one Eli- gen (cloning) and one Eli- (gen + 1) (cloned) exist as a result of Eli-gen 's cloning.) This action takes gen \times C ( C is a coefficient related to cloning. ) seconds.
• Hand out one leaflet. This action takes one second regardress of the generation ( =gen ).

They can not hand out leaflets while cloning. Given N and C , find the maximum number of leaflets Eli- 1 and her clones can hand out in total modulo 1000000007 (= 10^9 + 7).

Constraints

• 1 \leq Q \leq 100000 = 10^5
• 1 \leq N_q \leq 100000 = 10^5
• 1 \leq C_q \leq 20000 = 2 \times 10^4

Sample Input 1

2
20 8
20 12

Sample Output 1

24
20

For the first test case, while only 20 leaflets can be handed out without cloning, 24 leaflets can be handed out by cloning first and two people handing out12 leaflets each.

For the second test case, since two people can only hand out 8 leaflets each if Eli- 1 clones, she should hand out 20 leaflets without cloning.

Sample Input 2

1
20 3

Sample Output 2

67

One way of handing out 67 leaflets is like the following image. Each black line means cloning, and each red line means handing out.

This case satisfies the constraint of the partial score.

Sample Input 3

1
200 1

Sample Output 3

148322100

Note that the value modulo 1000000007 ( 10^9 + 7 ) must be printed.

This case satisfies the constraint of the partial score.

Problem Statement

Mikan's birthday is coming soon. Since Mikan likes graphs very much, Aroma decided to give her a undirected graph this year too.

Aroma bought a connected undirected graph, which consists of n vertices and n edges. The vertices are numbered from 1 to n and for each i(1 \leq i \leq n), vertex i and vartex a_i are connected with an undirected edge. Aroma thinks it is not interesting only to give the ready-made graph and decided to paint it. Count the number of ways to paint the vertices of the purchased graph in k colors modulo 10^9 + 7. Two ways are considered to be the same if the graph painted in one way can be identical to the graph painted in the other way by permutating the numbers of the vertices.

Constraints

• 1 \leq n \leq 10^5
• 1 \leq k \leq 10^5
• 1 \leq a_i \leq n (1 \leq i \leq n)
• The given graph is connected
• The given graph contains no self-loops or multiple edges.

Sample Input 1

4 2
2
3
1
1

Sample Output 1

12

Sample Input 2

4 4
2
3
4
1

Sample Output 2

55

Sample Input 3

10 5
2
3
4
1
1
1
2
3
3
4

Sample Output 3

926250

Story

I am a Summoner who can invoke monsters. I can embody the pictures of monsters drawn on sketchbooks.

I recently have received a request from Primate Research Institute of Kyoto University to invoke "Hundred Eyes Monster".

What an great honor it is to contribute to the prosperity of the primate research of Kyoto University! I decided to paint an extremely high-quarity monster to the best of my ability.

I have already painted the forehead and mouth and this time I am going to paint as many eyes as possible between the forehead and mouth. Well...I cannot wait to see the complete painting.

Problem Statement

Two circles A, B are given on a two-dimensional plane. The coordinate of the center and radius of circle A is (x_A, y_A) and r_A respectively. The coordinate of the center and radius of circle B is (x_B, y_B) and r_B respectively. These two circles have no intersection inside. Here, we consider a set of circles S that satisfies the following conditions.

• Each circle in S touches both A and B, and does not have common points with them inside the circle.
• Any two different circles in S have no common points inside them.

Write a program that finds the maximum number of elements in S.

Constraints

• 1 \leq T \leq 50000
• -10^5 \leq x_A \leq 10^5
• -10^5 \leq y_A \leq 10^5
• -10^5 \leq x_B \leq 10^5
• -10^5 \leq y_B \leq 10^5
• 1 \leq r_A \leq 10^5
• 1 \leq r_B \leq 10^5
• {r_A}^2 + {r_B}^2 < (x_A - x_B)^2 + (y_A - y_B)^2
• All values given as input are integers.
• It is guaranteed that, when the radiuses of A and B change by 0.0005, the answer does not change.

Sample Input 1

4
0 -3 2 0 3 2
0 0 9 8 8 2
0 0 9 10 10 5
0 0 707 1000 1000 707

Sample Output 1

3
10
21
180