Hôm nay, kênh TL chanel của anh Lộc vừa dạy một công thức nâng cao về tính diện tích tam giác, đó là tính diện tích dựa vào độ dài 3 đường cao ~x, y, z.~

Bạn Tài dù không học được bài giảng này nhưng cũng đã xin được bộ test case của anh Lộc về để học. Bây giờ ứng với mỗi test gồm 3 số nguyên dương, Tài cần kiểm tra xem các số này có tạo thành 3 đường cao của tam giác nào đó hay không? Nếu không thì in ra ~-1~, nếu có thì in ra diện tích của tam giác tương ứng, làm tròn đến ~2~ chữ số thập phân. Hãy giúp Tài thử sức nhé, nếu làm không được thì Tài phải nạp tiền để đăng ký học thôi.

Input

Một dòng duy nhất gồm 3 số nguyên dương ~x,y,z~ không quá ~2023.~

Output

Đáp số của bài toán.

Sample input 1

1 1 1

Sample output 1

0.58

Sample input 2

1 2 3

Sample output 2

-1

Hàng của cô Ban hôm nay có nhập về một số lượng lớn kẹo, gồm ~n~ viên. Khách hàng thân thiết của cô là anh Mạnh và anh Vũ. Mạnh sẽ chọn trước một số ~k~ nguyên. Mỗi ngày Mạnh sẽ ăn ~k~ viên vào buổi sáng và Vũ sẽ 1/10 số kẹo còn lại vào buổi chiều (nếu số kẹo còn lại không chia hết cho 10 thì làm tròn xuống). Ngày nào cũng lặp lại như thế, đến khi ăn hết kẹo thì thôi. Mạnh muốn giành được sự quan tâm từ cô Ban nên muốn chọn số ~k~ sao cho số kẹo mà Mạnh ăn là >= số kẹo mà Vũ ăn. Bạn hãy giúp Mạnh tìm ra ~k~ nhỏ nhất để được điều này nhé.

Input

Một dòng duy nhất là số nguyên dương ~n~ với ~1 \le n \le 10^{18}.~

Output

Số ~k~ cần tìm.

Sample input

68

Sample output

3

*Giải thích: * với ~k=3~ viên thì quá trình ăn kẹo của các ngày sẽ diễn ra như sau:

~(65,59) \to (56,51) \to (48,44) \to (41,37) \to (34,31) \to (28,26) \to (23,21) \to (18,17) \to (14,13) \to (10,9) \to (6,6) \to (3,3) \to (0,0).~

Ta tính được Mạnh ăn ~39~ viên kẹo, nếu chọn ~k = 2~ thì số lượng này sẽ ít hơn.

Thầy Luna đang muốn thêu các chữ ~L~ ứng với tên để gắn lên các chai nước suối cũng như các cây bút bi của mình, vì thầy ấy hay bị thầy Tina lấy nhầm. Thầy đã mua sẵn một mảnh vải kích thước ~2 \times n~ được chia thành ~2n~ và muốn cắt ra từ đó các chữ chữ ~L~ (kích thước ~3~ ô). Chữ ~L~ xoay theo hướng nào cũng được vì kiểu gì thì cũng dùng để dán thôi. Tuy nhiên, tấm vải vừa mua xong đã bị bạn Phú phá phách dùng để lấy làm giẻ lau và dơ một vài chỗ. Thầy Luna vẫn cố gắng tận dụng các phần sạch còn lại để dùng, hỏi thầy cắt ra được nhiều nhất bao nhiêu chữ ~L~?

Input

Hai dòng, mỗi dòng gồm ~n~ ký tự ~0~ (số không) và ~X~, trong đó ~0~ là phần vải sạch, còn ~X~ là phần bị dơ. Độ dài ~n~ thỏa mãn ~1 \le n \le 100.~

Output

Số chữ ~L~ tối đa có thể cắt được.

Sample input 1

00
00

Sample output 1

1

Sample input 2

00XXXX0XXX0
0XXXXX00X00

Sample output 1

3

Sample input 1

0XXX0
0X0X0

Sample output 1

0

Thầy Tina, vào một ngày mùa xuân xa xôi, ngồi trên xe bus để đi thăm các học trò cũ. Thầy muốn đón một tuyến xe bus có mã số ~X~ nhưng do mắt mờ nên thầy đọc nhầm sang số ~X'~, bị đảo lộn thứ tự và hiện tại thầy cũng không nhớ số xe ~X~ là số nào. Tuy nhiên, thầy biết chắc một điều rằng: số xe bus sẽ không bắt đầu bằng số ~0~, ngoài ra chữ số nào có trong ~X'~ thì chắc chắn cũng sẽ có trong ~X~ nhưng số lần có thể ít hơn, đáng tiếc là các chữ cái bị đảo lộn hơi nhiều. Bây giờ thầy phải đi check từng khả năng của số ~X~ rồi hỏi các học trò của mình. Thời gian không còn nhiều và mùa xuân sắp hết, bạn hãy giúp thầy Tina đếm xem cần phải check bao nhiêu lâu nữa nhé.

Input

Một số nguyên dương ~n~ duy nhất là biển số xe ~X'~ mà thầy đọc nhầm, với ~1 \le n \le 10^{18}.~

Output

Số tất cả khả năng của biển số xe ~X~ ban đầu, cho biết rằng số này có thể tính trong kiểu Int64.

Sample input 1

56

Sample output 1

2

Sample input 2

2024

Sample output 2

13

Sample input 3

1234

Sample output 3

24

Sample input 4

50

Sample output 4

1

Giải thích: trong VD1, chỉ có 2 khả năng là ~56,65~; còn trong VD2, có các khả năng là: ~204, 240, 420, 2024, 2042, 2204, 2240, 2402, 2420, 4022, 4202, 4220.~ Trong VD3, tất cả các chữ số đều phải có mặt trong ~X~ nên sẽ có ~4! = 24~ khả năng, còn trong VD4, ~X~ chỉ có thể là ~50~ chứ không là ~05~ nên có 1 khả năng duy nhất.

Với một khao khát trở thành một vận động viên chạy marathon thực thụ trên con đường Olympic, thầy Luna rất hào hứng khi tạo ra một đường đua chạy marathon cho những SV của mình, điều mà thầy đã từng không làm được. Thầy vừa tạo ra một tuyến đường gồm ~n~ cột mốc trong mặt phẳng tọa độ Oxy được đánh số theo thứ tự từ ~1~ đến ~n~. Không may thay, thầy nhận ra rằng những SV có thể không có đủ thể lực để chạy hết quãng đường này. Vì vậy thầy muốn biết độ dài của một số đoạn đường con nhất định: bắt đầu từ cột mốc ~i~ và kết thúc tại cột mốc ~j~, SV phải tìm đường đi trên đoạn này có độ dài nhỏ nhất. Vì đường đua được thiết kế ở khu vụ trung tâm thành phố gồm mạng lưới các đường phố nên khoảng cách giữa hai cột mốc ~(x_1, y_1)~ và ~(x_2, y_2)~ là ~|x_1-x_2| + |y_1-y_2|~. Ngoài ra, để xây dựng đường đua chạy marathon tốt nhất có thể, thầy muốn tìm ra sự ảnh hưởng của việc thay đổi những cột mốc mà thầy đã có trên đường đua hiện tại. Hãy giúp thầy xác định những thay đổi cột mốt này sẽ ảnh hưởng tới thời gian cần thiết để những SV chạy những tuyến đường con khác nhau như thế nào?

Input

Dòng đầu tiên ghi hai số nguyên dương ~n,Q~ với ~1≤n, Q≤10^5~, trong ~n~ dòng tiếp theo, mỗi dòng ghi hai số nguyên ~x,y~ là tọa độ một cột mốc theo thứ tự mà các SV phải chạy qua trên tuyến đường. Tọa độ có giá trị nằm trong khoảng ~[-10^3,10^3]~.

Trong ~Q~ dòng tiếp theo, mỗi dòng mô tả một câu hỏi hoặc một thay đổi cần thực hiện theo thứ tự. Nó sẽ có một trong hai dạng:

• U i x y: điểm cột mốc ~i~ sẽ được di chuyển đến vị trí ~(x,y)~
• Q i j : thời cần thiết nhỏ nhất để chạy từ cột mốc ~i~ đến cột mốc ~j~ với ~i≤j~ với điều kiện những SV có thể bỏ qua một cột mốc dọc theo tuyến đường từ ~i~ đến ~j~ (không bao gồm ~i~ và ~j~.

Output:

Với mỗi câu hỏi về thời gian đi trên một tuyến đường in ra một số nguyên trên một dòng là thời gian nhỏ nhất tìm được.

Sample input

5 5
-4 4
-5 -3
-1 5
-3 4
0 5
Q 1 5
U 4 0 1
U 4 -1 1
Q 2 4
Q 1 4

Sample output

11
8
8

Đa thức ~P(x)~ hệ số nguyên, khác ~0,~ được gọi là liên kết với số nguyên dương ~m~ nếu như với mọi số ~a~ nguyên tùy ý thì đều có ~P(a)~ chia hết cho ~m~. Hãy xác định bậc nhỏ nhất của một đa thức nguyên nào đó có thể liên kết với ~m~.

Input

Một dòng duy nhất là số nguyên dương ~m~ với ~1 \le m \le 10^{14}.~

Output

Đáp số của bài toán.

Sample input 1

2

Sample output 1

2

Sample input 2

6

Sample output 2

3

Giải thích: trong VD1, ta cần tìm đa thức ~P(x)~ mà ~P(x)~ chia hết cho ~2~ với mọi ~x~ nguyên, dễ thấy bậc 1 không thỏa mãn, bậc hai thì có thể chọn ~P(x) = x(x-1)~ luôn chẵn với mọi ~x~ nguyên; trong VD2, ta chọn đa thức ~P(x) = x(x-1)(x-2)~ luôn chia hết cho ~2~ và ~3~ nên sẽ chia hết cho ~6.~

Cho một cây có trọng số gồm ~N~ đỉnh và ~N – 1~ cạnh. Gọi ~D(i, j)~ là khoảng cách từ đỉnh ~i~ đến đỉnh ~j~ trên cây. Tạo đồ thị có hướng mới gồm ~N~ đỉnh, với mỗi cặp đỉnh ~(i, j)~ nếu ~i < j~ thì thêm cạnh nối từ đỉnh ~i~ đến đỉnh ~j~ có trọng số là ~D(i, j).~ Nhiệm vụ của bạn là hãy tìm đường đi ngắn nhất từ đỉnh 1 đến tất cả các đỉnh khác trong đồ thị mới tạo.

Input dòng đầu gồm số nguyên ~N~ với ~2 ≤ N ≤ 8.10^4~. Tiếp theo, dòng thứ ~i~ với ~1 ≤ i ≤ N - 1~ bao gồm 3 số nguyên: ~u_i, v_i, w_i~ với ~1 ≤ u_i < v_i ≤ N, |w_i | ≤ 10^9~, với ý nghĩa có cạnh nối giữa ~u_i~ và ~v_i~ với trọng số ~w_i~. Tất cả các cạnh này mô tả cây ban đầu.

Output gồm ~N~ số nguyên, số nguyên thứ ~i~ cho biết cho đường đi ngắn nhất từ 1 đến i trên đồ thị mới.

Sample input

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

Sample output

0 -2 -3 1 -10

Giải thích

• ~1 \to 2~ với chi phí ~D(1, 2) = -2~
• ~1 \to 2 \to 3~ với chi phí ~D(1, 2) + D(2, 3) = -3~
• ~1 \to 2 \to 3 \to 4~ với chi phí ~D(1, 2) + D(2, 3) + D(3, 4) = 1~
• ~1 \to 2 \to 3 \to 5~ với chi phí ~D(1, 2) + D(2, 3) + D(3, 5) = -10~