Problem Statement

There are ~N~ students in a school.

We will divide these students into some groups, and in each group they will discuss some themes.

You think that groups consisting of two or less students cannot have an effective discussion, so you want to have as many groups consisting of three or more students as possible.

Divide the students so that the number of groups consisting of three or more students is maximized.

Constraints

• ~1 \leq N \leq 1000~
• All input values are integers.

Input

Input is given from Standard Input in the following format:

~N~

Output

If you can form at most ~x~ groups consisting of three or more students, print ~x~ .

Sample Input 1

8

Sample Output 1

2

For example, you can form a group of three students and another of five students.

Sample Input 2

2

Sample Output 2

0

Sometimes you cannot form any group consisting of three or more students, regardless of how you divide the students.

Sample Input 3

9

Sample Output 3

3

Problem Statement

You are given a three-digit positive integer ~N~ .
Determine whether ~N~ is a palindromic number .
Here, a palindromic number is an integer that reads the same backward as forward in decimal notation.

Constraints

• ~100≤N≤999~
• ~N~ is an integer.

Input

Input is given from Standard Input in the following format:

~N~

Output

If ~N~ is a palindromic number, print Yes ; otherwise, print No .

Sample Input 1

575

Sample Output 1

Yes

~N=575~ is also ~575~ when read backward, so it is a palindromic number. You should print Yes .

Sample Input 2

123

Sample Output 2

No

~N=123~ becomes ~321~ when read backward, so it is not a palindromic number. You should print No .

Sample Input 3

812

Sample Output 3

No

Problem Statement

Chuyện kể rằng có 1 chàng trai Japan thích ăn bánh quy, một ngày đẹp trai anh mua một túi bánh

Và vẫn như thường ngày anh vẫn hay đếm số màu bánh có được trong chiếc túi. Nhưng hôm nay công việc này quá đơn giản nên anh ấy quyết định giao lại cho bạn

Chiếc túi có chứa ~N~ Bánh quy

Được biết, chiếc túi có chứa bánh quy với 3 màu: hồng, trắng và xanh lá cây, hoặc chứa arare với 4 màu: hồng, trắng, xanh lá và vàng.

Được ký hiệu như sau Hồng: P , Trắng: W , Xanh: G , Vàng: Y .

Nếu số màu trong chiếc túi là ba thì hãy in Three ; ngược lại in Four .

Constraints

• ~1 \leq N \leq 100~
• ~S_i~ is P , W , G or Y .
• Luôn tồn tại ~i~ , ~j~ và ~k~ sao cho ~S_i=~ P , ~S_j=~ W và ~S_k=~ G .

Input

Đầu vào được mô tả như sau:

~N~

~S_1~ ~S_2~ ~...~ ~S_N~

Output

Nếu số màu trong chiếc túi là ba thì hãy in Three ; ngược lại in Four .

Sample Input 1

6
G W Y P Y W

Sample Output 1

Four

Sample Input 2

9
G W W G P W P G G

Sample Output 2

Three

Sample Input 3

8
P Y W G Y W Y Y

Sample Output 3

Four

Problem Statement

Alice and Bob are controlling a robot. They each have one switch that controls the robot.
Alice started holding down her button ~A~ second after the start-up of the robot, and released her button ~B~ second after the start-up.
Bob started holding down his button ~C~ second after the start-up, and released his button ~D~ second after the start-up.
For how many seconds both Alice and Bob were holding down their buttons?

Constraints

• ~0≤A<B≤100~ </li>
• ~0≤C<D≤100~ </li>
• All input values are integers.

Input

Input is given from Standard Input in the following format:

~A~ ~B~ ~C~ ~D~

Output

Print the length of the duration (in seconds) in which both Alice and Bob were holding down their buttons.

Sample Input 1

0 75 25 100

Sample Output 1

50

Alice started holding down her button ~0~ second after the start-up of the robot, and released her button ~75~ second after the start-up.
Bob started holding down his button ~25~ second after the start-up, and released his button ~100~ second after the start-up.
Therefore, the time when both of them were holding down their buttons, is the ~50~ seconds from ~25~ seconds after the start-up to ~75~ seconds after the start-up.

Sample Input 2

0 33 66 99

Sample Output 2

0

Alice and Bob were not holding their buttons at the same time, so the answer is zero seconds.

Sample Input 3

10 90 20 80

Sample Output 3

60

Problem Statement

Trong một game show Có ~N~ người. Tên của ngưởi thứ ~i~ -th là ~S_i~ .

Người tổ chức trò chơi muốn chọn 3 người trong số họ thỏa mãn điều kiện sau:

• Tên của mỗi người được chọn phải được bắt đầu bằng các chữ cái sau M , A , R , C hoặc H .
• Những người được chọn có tên bắt đầu đều không cùng thuộc một chữ cái.

Hỏi có bao nhiêu cách chọn ba người như vậy mà không quan tâm đến thứ tự?

Constraints

• ~1 \leq N \leq 10^5~
• ~S_i~ đều là các chữ cái tiếng anh viết thường.
• ~1 \leq |S_i| \leq 10~
• ~S_i \neq S_j (i \neq j)~

Input

Đầu vào được cung cấp từ Đầu vào chuẩn ở định dạng sau:

~N~

~S_1~

~:~

~S_N~

Output

Nếu có ~ x ~ cách chọn ba người sao cho thỏa mãn các điều kiện đã cho, in ra ~ x ~.

Sample Input 1

5
MASHIKE
RUMOI
OBIRA
HABORO
HOROKANAI

Sample Output 1

2

Chúng ta có thể chọn ba người có tên sau:

• MASHIKE , RUMOI , HABORO

• MASHIKE , RUMOI , HOROKANAI

Sample Input 2

4
ZZ
ZZZ
Z
ZZZZZZZZZZ

Sample Output 2

0

Sample Input 3

5
CHOKUDAI
RNG
MAKOTO
AOKI
RINGO

Sample Output 3

7

Problem Statement

We have ~N~ clocks. The hand of the ~i~ -th clock ~(1≤i≤N)~ rotates through ~360°~ in exactly ~T_i~ seconds.
Initially, the hand of every clock stands still, pointing directly upward.
Now, Dolphin starts all the clocks simultaneously.
In how many seconds will the hand of every clock point directly upward again?

Constraints

• ~1≤N≤100~
• ~1≤T_i≤10^{18}~
• All input values are integers.
• The correct answer is at most ~10^{18}~ seconds.

Input

Input is given from Standard Input in the following format:

~N~

~T_1~

~:~

~T_N~

Output

Print the number of seconds after which the hand of every clock point directly upward again.

Sample Input 1

2
2
3

Sample Output 1

6

We have two clocks. The time when the hand of each clock points upward is as follows:

• Clock ~1~ : ~2~ , ~4~ , ~6~ , ~...~ seconds after the beginning
• Clock ~2~ : ~3~ , ~6~ , ~9~ , ~...~ seconds after the beginning

Therefore, it takes ~6~ seconds until the hands of both clocks point directly upward.

Sample Input 2

5
2
5
10
1000000000000000000
1000000000000000000

Sample Output 2

1000000000000000000

Problem Statement

We have a grid with ~H~ rows and ~W~ columns. The square at the ~i~ -th row and the ~j~ -th column will be called Square ~(i,j)~ .

The integers from ~1~ through ~H×W~ are written throughout the grid, and the integer written in Square ~(i,j)~ is ~A_{i,j}~ .

You, a magical girl, can teleport a piece placed on Square ~(i,j)~ to Square ~(x,y)~ by consuming ~|x-i|+|y-j|~ magic points.

You now have to take ~Q~ practical tests of your ability as a magical girl.

The ~i~ -th test will be conducted as follows:

• Initially, a piece is placed on the square where the integer ~L_i~ is written.

• Let ~x~ be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer ~x+D~ is written, as long as ~x~ is not ~R_i~ . The test ends when ~x=R_i~ .

• Here, it is guaranteed that ~R_i-L_i~ is a multiple of ~D~ .

For each test, find the sum of magic points consumed during that test.

Constraints

• ~1 \leq H,W \leq 300~
• ~1 \leq D \leq H×W~
• ~1 \leq A_{i,j} \leq H×W~
• ~A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))~
• ~1 \leq Q \leq 10^5~
• ~1 \leq L_i \leq R_i \leq H×W~
• ~(R_i-L_i)~ is a multiple of ~D~ .

Input

Input is given from Standard Input in the following format:

~H~ ~W~ ~D~

~A_{1,1}~ ~A_{1,2}~ ~...~ ~A_{1,W}~

~:~

~A_{H,1}~ ~A_{H,2}~ ~...~ ~A_{H,W}~

~Q~

~L_1~ ~R_1~

~:~

~L_Q~ ~R_Q~

Output

For each test, print the sum of magic points consumed during that test.

Output should be in the order the tests are conducted.

Sample Input 1

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

Sample Output 1

5

• ~4~ is written in Square ~(1,2)~ .

• ~6~ is written in Square ~(3,3)~ .

• ~8~ is written in Square ~(3,1)~ .

Thus, the sum of magic points consumed during the first test is ~(|3-1|+|3-2|)+(|3-3|+|1-3|)=5~ .

Sample Input 2

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

Sample Output 2

0
0

Note that there may be a test where the piece is not moved at all, and there may be multiple identical tests.

Sample Input 3

5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13

Sample Output 3

0
5
0

Mô tả vấn đề

Bạn được cho một cây với ~N~ đỉnh.
Biết rằng, cây là một dạng đồ thị, và cụ thể hơn là một đồ thị vô hướng được kết nối với ~N-1~ cạnh, với ~N~ là số đỉnh của cây.
Cạnh thứ ~i~-th ~(1≤i≤N-1)~ được kết nối với đỉnh ~a_i~ và ~b_i~ , và có độ dài cạnh là ~c_i~ .

Bạn được cung cấp ~Q~ truy vấn và số nguyên ~K~ .Ở truy vấn thứ ~j~ -th ~(1≤j≤Q)~ :

• Hãy tìm khoảng cách ngắn nhất đi từ đỉnh ~x_j~ qua ~y_j~ và đi qua đỉnh ~K~ .

Mô tả đầu vào

• ~3≤N≤10^5~
• ~1≤a_i,b_i≤N (1≤i≤N-1)~
• ~1≤c_i≤10^9 (1≤i≤N-1)~
• The given graph is a tree.
• ~1≤Q≤10^5~
• ~1≤K≤N~
• ~1≤x_j,y_j≤N (1≤j≤Q)~
• ~x_j≠y_j (1≤j≤Q)~
• ~x_j≠K,y_j≠K (1≤j≤Q)~

Input

~N~

~a_1~ ~b_1~ ~c_1~

~:~

~a_{N-1}~ ~b_{N-1}~ ~c_{N-1}~

~Q~ ~K~

~x_1~ ~y_1~

~:~

~x_{Q}~ ~y_{Q}~

Output

In ra ~Q~ dòng.
Với dòng thứ ~j~th ~j(1≤j≤Q)~ ,in ra khoảng cách ngắn nhất theo yêu cầu.

Sample Input 1

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

Sample Output 1

3
2
4

Các đường dẫn ngắn nhất cho ba truy vấn như sau:

• Truy vấn ~1~ : Đỉnh ~2~ → Đỉnh ~1~ → Đỉnh ~2~ → Đỉnh ~4~ : Khoảng cách ~1+1+1=3~
• Truy vấn ~2~ : Đỉnh ~2~ → Đỉnh ~1~ → Đỉnh ~3~ : Khoảng cách ~1+1=2~
• truy vấn ~3~ : Đỉnh ~4~ → Đỉnh ~2~ → Đỉnh ~1~ → Đỉnh ~3~ → Đỉnh ~5~ : Khoảng cách ~1+1+1+1=4~

Sample Input 2

7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7

Sample Output 2

5
14
22

Sample Input 3

10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10

Sample Output 3

17000000000