Problem Statement

There is a box containing N balls. The i-th ball has the integer A_i written on it. Snuke can perform the following operation any number of times:

• Take out two balls from the box. Then, return them to the box along with a new ball, on which the absolute difference of the integers written on the two balls is written.

Determine whether it is possible for Snuke to reach the state where the box contains a ball on which the integer K is written.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq K \leq 10^9
• All input values are integers.

Sample Input 1

3 7
9 3 4

Sample Output 1

POSSIBLE

First, take out the two balls 9 and 4, and return them back along with a new ball, abs(9-4)=5. Next, take out 3 and 5, and return them back along with abs(3-5)=2. Finally, take out 9 and 2, and return them back along with abs(9-2)=7. Now we have 7 in the box, and the answer is therefore POSSIBLE.

Sample Input 2

3 5
6 9 3

Sample Output 2

IMPOSSIBLE

No matter what we do, it is not possible to have 5 in the box. The answer is therefore IMPOSSIBLE.

Sample Input 3

4 11
11 3 7 15

Sample Output 3

POSSIBLE

The box already contains 11 before we do anything. The answer is therefore POSSIBLE.

Sample Input 4

5 12
10 2 8 6 4

Sample Output 4

IMPOSSIBLE

Problem Statement

Takahashi is hosting an sports meet. There are N people who will participate. These people are conveniently numbered 1 through N. Also, there are M options of sports for this event. These sports are numbered 1 through M. Among these options, Takahashi will select one or more sports (possibly all) to be played in the event.

Takahashi knows that Person i's j-th favorite sport is Sport A_{ij}. Each person will only participate in his/her most favorite sport among the ones that are actually played in the event, and will not participate in the other sports.

Takahashi is worried that one of the sports will attract too many people. Therefore, he would like to carefully select sports to be played so that the number of the participants in the sport with the largest number of participants is minimized. Find the minimum possible number of the participants in the sport with the largest number of participants.

Constraints

• 1 \leq N \leq 300
• 1 \leq M \leq 300
• A_{i1} , A_{i2} , ... , A_{iM} is a permutation of the integers from 1 to M.

Sample Input 1

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

Sample Output 1

2

Assume that Sports 1, 3 and 4 are selected to be played. In this case, Person 1 will participate in Sport 1, Person 2 in Sport 3, Person 3 in Sport 3 and Person 4 in Sport 4. Here, the sport with the largest number of participants is Sport 3, with two participants. There is no way to reduce the number of participants in the sport with the largest number of participants to 1. Therefore, the answer is 2.

Sample Input 2

3 3
2 1 3
2 1 3
2 1 3

Sample Output 2

3

Since all the people have the same taste in sports, there will be a sport with three participants, no matter what sports are selected. Therefore, the answer is 3.

Problem Statement

There are X+Y+Z people, conveniently numbered 1 through X+Y+Z. Person i has A_i gold coins, B_i silver coins and C_i bronze coins.

Snuke is thinking of getting gold coins from X of those people, silver coins from Y of the people and bronze coins from Z of the people. It is not possible to get two or more different colors of coins from a single person. On the other hand, a person will give all of his/her coins of the color specified by Snuke.

Snuke would like to maximize the total number of coins of all colors he gets. Find the maximum possible number of coins.

Constraints

• 1 \leq X
• 1 \leq Y
• 1 \leq Z
• X+Y+Z \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• 1 \leq C_i \leq 10^9

Sample Input 1

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

Sample Output 1

18

Get silver coins from Person 1, silver coins from Person 2, bronze coins from Person 3 and gold coins from Person 4. In this case, the total number of coins will be 4+2+7+5=18. It is not possible to get 19 or more coins, and the answer is therefore 18.

Sample Input 2

3 3 2
16 17 1
2 7 5
2 16 12
17 7 7
13 2 10
12 18 3
16 15 19
5 6 2

Sample Output 2

110

Sample Input 3

6 2 4
33189 87907 277349742
71616 46764 575306520
8801 53151 327161251
58589 4337 796697686
66854 17565 289910583
50598 35195 478112689
13919 88414 103962455
7953 69657 699253752
44255 98144 468443709
2332 42580 752437097
39752 19060 845062869
60126 74101 382963164

Sample Output 3

3093929975

Problem Statement

There is a tree with N vertices, numbered 1 through N. The i-th edge in this tree connects Vertices A_i and B_i and has a length of C_i.

Joisino created a complete graph with N vertices. The length of the edge connecting Vertices u and v in this graph, is equal to the shortest distance between Vertices u and v in the tree above.

Joisino would like to know the length of the longest Hamiltonian path (see Notes) in this complete graph. Find the length of that path.

Notes

A Hamiltonian path in a graph is a path in the graph that visits each vertex exactly once.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq A_i < B_i \leq N
• The given graph is a tree.
• 1 \leq C_i \leq 10^8
• All input values are integers.

Sample Input 1

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

Sample Output 1

38

The length of the Hamiltonian path 5 → 3 → 1 → 4 → 2 is 5+8+15+10=38. Since there is no Hamiltonian path with length 39 or greater in the graph, the answer is 38.

Sample Input 2

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

Sample Output 2

132

Problem Statement

Joisino is planning on touring Takahashi Town. The town is divided into square sections by north-south and east-west lines. We will refer to the section that is the x-th from the west and the y-th from the north as (x,y).

Joisino thinks that a touring plan is good if it satisfies the following conditions:

• Let (p,q) be the section where she starts the tour. Then, X_1 \leq p \leq X_2 and Y_1 \leq q \leq Y_2 hold.

• Let (s,t) be the section where she has lunch. Then, X_3 \leq s \leq X_4 and Y_3 \leq t \leq Y_4 hold.

• Let (u,v) be the section where she ends the tour. Then, X_5 \leq u \leq X_6 and Y_5 \leq v \leq Y_6 hold.

• By repeatedly moving to the adjacent section (sharing a side), she travels from the starting section to the ending section in the shortest distance, passing the lunch section on the way.

Two touring plans are considered different if at least one of the following is different: the starting section, the lunch section, the ending section, and the sections that are visited on the way. Joisino would like to know how many different good touring plans there are. Find the number of the different good touring plans. Since it may be extremely large, find the count modulo 10^9+7.

Constraints

• 1 \leq X_1 \leq X_2 < X_3 \leq X_4 < X_5 \leq X_6 \leq 10^6
• 1 \leq Y_1 \leq Y_2 < Y_3 \leq Y_4 < Y_5 \leq Y_6 \leq 10^6

Sample Input 1

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

Sample Output 1

10

The starting section will always be (1,1), and the lunch section will always be (2,2). There are four good touring plans where (3,3) is the ending section, and six good touring plans where (4,3) is the ending section. Therefore, the answer is 6+4=10.

Sample Input 2

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

Sample Output 2

2346

Sample Input 3

77523 89555 420588 604360 845669 973451
2743 188053 544330 647651 709337 988194

Sample Output 3

137477680

Problem Statement

There are two rooted trees, each with N vertices. The vertices of each tree are numbered 1 through N. In the first tree, the parent of Vertex i is Vertex A_i. Here, A_i=-1 if Vertex i is the root of the first tree. In the second tree, the parent of Vertex i is Vertex B_i. Here, B_i=-1 if Vertex i is the root of the second tree.

Snuke would like to construct an integer sequence of length N, X_1 , X_2 , ... , X_N, that satisfies the following condition:

• For each vertex on each tree, let the indices of its descendants including itself be a_1 , a_2 , ..., a_k. Then, abs(X_{a_1} + X_{a_2} + ... + X_{a_k})=1 holds.

Determine whether it is possible to construct such a sequence. If the answer is possible, find one such sequence.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i \leq N, if Vertex i is not the root in the first tree.
• A_i = -1, if Vertex i is the root in the first tree.
• 1 \leq B_i \leq N, if Vertex i is not the root in the second tree.
• B_i = -1, if Vertex i is the root in the second tree.
• Input corresponds to valid rooted trees.

Sample Input 1

5
3 3 4 -1 4
4 4 1 -1 1

Sample Output 1

POSSIBLE
1 -1 -1 3 -1

For example, the indices of the descendants of Vertex 3 of the first tree including itself, is 3,1,2. It can be seen that the sample output holds abs(X_3+X_1+X_2)=abs((-1)+(1)+(-1))=abs(-1)=1. Similarly, the condition is also satisfied for other vertices.

Sample Input 2

6
-1 5 1 5 1 3
6 5 5 3 -1 3

Sample Output 2

IMPOSSIBLE

In this case, constructing a sequence that satisfies the condition is IMPOSSIBLE.

Sample Input 3

8
2 7 1 2 2 1 -1 4
4 -1 4 7 4 4 2 4

Sample Output 3

POSSIBLE
1 2 -1 0 -1 1 0 -1