Marisa tin rằng danmaku hình tam giác là sặc sỡ nhất. Cho 3 điểm tọa độ nguyên trên lưới tọa độ ~Oxy~, hãy xác định xem 3 điểm này có tạo thành hình tam giác được hay không?

Input

• 3 điểm có tọa độ nguyên.

Output

• YES và NO tương ứng với có hoặc không tạo được hình tam giác.

Sample Test

Input 1

0 0 0 1 1 0

Output 1

YES

Input 2

727 1 727 2 727 3

Output 2

NO

Giới hạn

• Tọa độ các điểm có giá trị tuyệt đối không vượt quá ~10^9~.

Yakumo Ran rất giỏi toán, nhưng với những số rất lớn cô sẽ gặp khó khăn nên cô nhờ các bạn giúp bài toán sau.

Cho hai số nguyên dương ~a,b~, hãy tính: ~\sum_{i=a}^b~ ~⌊\sqrt{i}⌋~.

Ở đây, ~⌊a⌋~ có nghĩa là số nguyên lớn nhất không lớn hơn ~a~.

Input

• Gồm một dòng chứa hai số nguyên dương ~a,b~.

Output

• In ra kết quả của bài toán.

Sample Test

Input 1

3 10

Output 1

17

Giải thích

~⌊\sqrt{3}⌋+⌊\sqrt{4}⌋+⌊\sqrt{5}⌋+⌊\sqrt{6}⌋+⌊\sqrt{7}⌋+⌊\sqrt{8}⌋+⌊\sqrt{9}⌋+⌊\sqrt{10}⌋~ ~=1+2+2+2+2+2+3+3=17~

Input 2

14 29

Output 2

67

Giới hạn:

• Subtask 1 (60% số điểm): ~a,b \le 10^6~
• Subtask 2 (40% số điểm): ~a,b \le 10^{12}~

Năm ~404~ BC, vùng đất Westeros đang xôn xao vì một bài toán rất lạ được đưa ra từ một kẻ ẩn danh tới từ Essos. Khắp bảy phụ quốc, các lãnh chúa liên tục tìm người để giải quyết bài toán nhưng đều thất bại. Bài toán được lan truyền tới Oldtown và khiến các Maester ở Citadel cũng phải đau đầu. Hãy giúp các học sĩ giải quyết bài toán này nhé:

Số đẹp được định nghĩa là một số nguyên dương và chia hết cho một trong ba số: ~3~, ~5~, hoặc ~7~.

Ví dụ về dãy các số đẹp: ~3, 5, 6, 7, 9, 10, 12, 14, 15, 18,...~

Hãy tìm số đẹp thứ ~k~.

Input

• Gồm một dòng chứa số nguyên dương ~k~.

Output

• In ra kết quả của bài toán.

Sample Test

Input 1

2

Output 1

5

Input 2

10

Output 2

18

Giới hạn:

• Subtask 1 (50% số điểm): ~k \le 10^6~
• Subtask 2 (50% số điểm): ~k \le 10^9~

Vườn hoa hướng dương của Kazami Yuuka có thể được biểu diễn bằng một ma trận ~n \times n~ trong đó mỗi ô ~(i, j)~ chứa một số nguyên dương là độ đẹp của bông hoa ở ô ~(i, j)~.

Yuuka mượn được của Kawashiro một chiếc máy hái hoa có bán kính ~k~, nói cách khác nếu sử dụng máy ở vị trí ~(i, j)~ thì có thể hái được những bông hoa ở vị trí ~(x, y)~ nếu ~|i - x| + |j - y| \le k~.

Muốn hái được những bông hoa đẹp nhất, cô nhờ các bạn, với mỗi vị trí của vườn hoa tính tổng độ đẹp những bông hoa hái được nếu sử dụng máy ở vị trí đó.

Input:

• Dòng đầu tiên gồm số nguyên dương ~n~ và ~k \le n~.
• ~n~ dòng tiếp theo mỗi dòng gồm ~n~ số nguyên không âm là độ đẹp của bông hoa, giá trị không vượt quá ~10^9~.

Output:

• In ra ma trận ~n \times n~ tương ứng

Sample Test

Input 1:

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

Output 1:

16 25 23 27 24 
21 35 41 36 27 
33 40 46 40 27 
36 47 42 38 29 
31 39 42 28 21 

Input 2:

3 1
1 0 2
0 0 1
1 0 0

Output 2:

1 3 3 
2 1 3 
1 1 1 

Giới hạn:

• Subtask 1 (40% số điểm): ~n \le 50~.
• Subtask 1 (30% số điểm): ~n \le 500~.
• Subtask 1 (30% số điểm): ~n \le 1000~.

Chim là loài động vật đại diện cho sự tự do. Châu có nuôi 1 con chim tên là Ển, hiện đang sống tại tọa độ ~(0, 0)~ trên mặt phẳng Descartes và hướng về phía dương của trục ~Ox~. Châu đang có một chuỗi thao tác gồm một số thao tác xác định và chưa xác định:

• ~F~ là 1 thao tác cố định yêu cầu chim đi chuyển 1 đơn vị về hướng hiện tại.
• ~T~ là 1 thao tác chưa xác định. Bạn có thể chọn T là cho chim quay theo chiều kim đồng hồ 90 độ hoặc cho chim quay theo ngược chiều kim đồng hộ 90 độ.

Có ~Q~ truy vấn tương ứng là ~Q~ tọa độ ~(x,y)~. Châu muốn biết xem có thể chọn các thao tác ~T~ tương ứng để chim đến được tọa độ ~(x,y)~ không.

Input:

• Dòng đầu tiên là ~Q~ – số lượng truy vấn.
• Dòng thứ hai là xâu biểu diện các thao tác.
• ~Q~ dòng tiếp theo mỗi dòng chứa tọa độ ~(x,y)~.

Output:

• Dòng thứ ~i~ trả về YES nếu chim có thể đến được ~(x,y)~ ở truy vấn thứ ~i~, ngược lại NO.

Sample Test

Input:

2
FTFFTFF
3 2
0 1

Output:

Yes
No

Giới hạn:

• Subtask 1 (20% số điểm): Độ dài các xâu không vượt quá ~20~ kí tự, ~Q \le 20~.
• Subtask 2 (40% số điểm): Độ dài các xâu không vượt quá ~100~ kí tự, ~Q \le 100~.
• Subtask 3 (40% số điểm): Độ dài các xâu không vượt quá ~4000~ kí tự, ~Q \le 10^5~.

Marisa sống trong khu rừng ma thuật. Một trong những việc cô thường làm là hái nấm.

Khu rừng có thể được biểu diễn bằng một cây có ~n~ nút, ở nút thứ ~i~ là loại nấm có màu ~c_i~. Do đây là khu rừng ma thuật nên các cây nấm có khả năng đổi màu.

Cho ~q~ ngày, mỗi ngày một trong hai sự kiện sau sẽ diễn ra:

• Cây nấm ở nút ~i~ đổi màu thành ~c~.
• Marisa đi hái nấm những cây nấm màu ~c~ từ nút ~u~ đến nút ~v~ theo đường đi ngắn nhất.

Với mỗi ngày Marisa đi hái nấm, hãy cho cô biết sẽ hái được bao nhiêu nấm nhé!

Input:

• Dòng đầu tiên là 2 số nguyên dương ~n, q~.
• Dòng tiếp theo gồm ~n~ số nguyên dương ~c_i \le n~ là màu của cây nấm ở đỉnh ~i~.
• ~n - 1~ dòng tiếp theo mỗi dòng là 2 số nguyên dương ~u, v \le n~ thể hiện có đường đi trực tiếp giữa nút ~u~ và ~v~.
• ~q~ dòng tiếp theo là một trong 2 loại:
  • 1 i c, đổi màu cây nấm ở nút ~i~ thành ~c~.
  • 2 u v c, Marisa hái nấm những cây nấm màu ~c~ từ nút ~u~ đến nút ~v~ theo đường đi ngắn nhất.

Output:

• Với mỗi ngày Marisa đi hái nấm, hãy in ra số lượng cây nấm cô hái được, cây nấm cô hái ngày hôm sau sẽ tự mọc lại và cùng màu với cây nấm cũ.

Sample Test:

Input:

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

Output:

2
2

Giới hạn:

• Subtask 1 (40% số điểm): ~n, q \le 1000~.
• Subtask 2 (30% số điểm): ~n, q \le 10^5~.
• Subtask 3 (30% số điểm): ~n, q \le 5 \times 10^5~.