Thi thử TS10 2024 - ngày 4

Rùa và Thỏ đang so tài với nhau xem ai chạy nhanh hơn. Trọng tài Cún sẽ quyết định xem ai chạy nhanh hơn, biết đường đua là một trục Ox.
Tuy nhiên vì ngủ quên nên Cún đã không biết ai chạy nhanh hơn ai. Cô chỉ biết rằng Rùa đã chạy từ điểm \(A\) đến điểm \(B\) trong \(t_1\) giây. Còn Thỏ thì đã mất \(t_2\) giây để đi từ \(C\) đến \(D\). Hãy giúp Cún tính xem ai chạy nhanh hơn. Trong khi di chuyển từ \(A\) đến \(B\) hay từ \(C\) đến \(D\), vận tốc của Rùa và Thỏ là không đổi.

Input

• Dòng đầu tiên nhập vào một số nguyên dương \(t\) (\(t \le 10^5\)) - số lượng truy vấn.
• \(t\) dòng tiếp theo, mỗi dòng nhập vào sáu số nguyên \(x_A, x_B, x_C, x_D, t_1, t_2\) (\(|x_A|, |x_B|, |x_C|, |x_D| \le 10^9\); \(0 < t_1, t_2 \le 10^9\)) - lần lượt là toạ độ các điểm \(A, B, C, D\), thời gian di chuyển của Rùa và Thỏ.

Output

• Với mỗi truy vấn, in ra Rua nếu như Rùa chạy nhanh hơn và in ra Tho trong trường hợp ngược lại. Nếu Rùa và Thỏ chạy nhanh như nhau, in ra Cun.
• Rùa và Thỏ được coi là chạy nhanh như nhau nếu chênh lệch vận tốc không vượt quá \(10^{-6}\).

Example

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

Rua
Cun
Tho

Cho 4 điểm \(A(x_A, y_A)\), \(B(x_B, y_B)\), \(C(x_C, y_C)\), \(D(x_D, y_D)\) trên hệ trục tọa độ Descartes.
Đường thẳng \((d)\) đi qua hai điểm \(A\) và \(B\). Đường thẳng \((d')\) đi qua hai điểm \(C\) và \(D\).
Gọi \(K(x_K, y_K)\) là giao điểm của hai đường thẳng \((d)\) và \((d')\).

Input

• Dòng đầu tiên nhập vào một số nguyên dương \(t\) (\(t \leq 10^5\)) - số lượng truy vấn.
• \(t\) dòng tiếp theo, mỗi dòng nhập vào tám số nguyên \(x_A, y_A, x_B, y_B, x_C, y_C, x_D, y_D\) (\(0 \leq |x_A|, |y_A|, |x_B|, |y_B|, |x_C|, |y_C|, |x_D|, |y_D| \leq 10^9\)) - toạ độ các điểm \(A, B, C, D\).

Output

• Với mỗi truy vấn, hãy in ra hai số \(x_K, y_K\) là toạ độ điểm \(K\) nếu hai đường thẳng có duy nhất \(1\) điểm chung. Nếu hai đường thẳng \((d)\) và \((d')\) có vô số điểm chung, in ra \(1000000000000000000\) (\(10^{18}\)). Còn nếu chúng không có điểm chung, in ra \(-1\).

Trong trường hợp hai đường thẳng \((d)\) và \((d')\) có duy nhất \(1\) điểm chung, kết quả của bạn sẽ được chấp nhận nếu sai số không vượt quá \(10^{-6}\).
Dữ liệu luôn đảm bảo \(|x_K|, |y_K| < 2^{63}\).

Example

4
0 1 1 0 0 2 2 0
0 0 1 1 -1 -1 -2 -2
1 1 4 2 3 3 2 1
3 1 5 5 4 2 1 1

-1
1000000000000000000
2.2 1.4
3.4 1.8

Hai chị em dinhkhanhha_ và dth đang chơi một trò chơi với xâu. dinhkhanhha_ sẽ chọn một xâu \(s\) với độ dài \(n\). Sau đó dth sẽ chọn ra \(k\) xâu con† của \(s\). Vì đã giống nhau sẵn nên lúc nào hai chị họ cũng muốn những điều khác biệt. Hãy giúp dth chọn sao cho số lượng xâu con phân biệt là tối đa.

†Xâu \(a\) được gọi là xâu con của xâu \(b\) nếu ta có thể thu được xâu \(a\) sau khi xoá một hoặc một vài (có thể không xoá) kí tự ở đầu và ở cuối của xâu \(b\).

Input

• Dòng đầu tiên nhập vào hai số nguyên dương \(n\), \(k\) - độ dài của xâu \(s\) và số xâu con cần chọn.
• Dòng tiếp theo, nhập vào một xâu \(s\) chỉ bao gồm các kí tự latin in thường.

Output

• Gồm một số nguyên dương duy nhất là kết quả của bài toán.

Example

3 7
aba

5

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 100\), \(k \le 10^{18}\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^5\), \(k \le 10^{18}\). Xâu \(s\) chỉ gồm \(1\) loại kí tự.
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 10^3\), \(k \le 10^{18}\).

Chữ số "rỗng" là chữ số có phần rỗng ở giữa. Các chữ số "rỗng" là \(0,\) \(4,\) \(6,\) \(8,\) \(9\).
Số "khác rỗng" là số mà không có chữ số "rỗng". Các số "khác rỗng" đầu tiên là \(1,\) \(2,\) \(3,\) \(5,\) \(7,\) ...

Input

• Dòng đầu tiên nhập vào một số nguyên dương \(t\) (\(t \le 10^4\)) - số lượng truy vấn.
• \(t\) dòng tiếp theo, mỗi dòng nhập vào một số nguyên dương \(n\) (\(n \le 10^{12}\)).

Output

• Với mỗi truy vấn, hãy in ra số "khác rỗng" thứ \(n\).
• Dữ liệu đảm bảo kết quả in ra luôn bé hơn \(2^{63}\).

Example

5
2 
4
16 
17
23

2
5
31
32
53

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(t \le 10\), \(n \le 10^4\).
• Subtask \(2\) (\(20\%\) số điểm): \(t \le 10^4\), \(n \le 10^5\).
• Subtask \(3\) (\(30\%\) số điểm): \(t \le 10^4\), \(n \le 10^{12}\).