Nguồn: Học sinh Giỏi THPT Hà Nội năm 2009 - 2010

Cho hai dãy số nguyên dương \(a_1, a_2, ..., a_m\) và \(b_1, b_2, ..., b_n\) . Từ hai dãy trên tạo ra \(m × n\) phân số \(a_i \over b_j\) với \(i = 1, 2, ..., m\), \(j = 1, 2, ..., n\). Sắp xếp các phân số vừa tạo theo thứ tự tăng dần sau khi đã tối giản và loại bớt các phân số bằng nhau (các phân số bằng nhau chỉ giữ lại một lần) thu được dãy phân số \(P\).

Ví dụ, dãy thứ nhất gồm \(2\) phần tử \(10, 30\); còn dãy thứ \(2\) gồm \(3\) phần tử \(20, 30, 60\) ta tạo được các phân số là: \(10 \over 20\), \(10 \over 30\), \(10 \over 60\), \(30 \over 20\), \(30 \over 30\), \(30 \over 60\) thì dãy phân số \(P\) là \(1 \over 6\), \(1 \over 3\), \(1 \over 2\), \(1 \over 1\), \(3 \over 2\).

Yêu cầu: Cho số nguyên dương \(k\), hãy tìm phân số thứ \(k\) trong dãy \(P\).

Input

Dữ liệu vào từ tệp văn bản PS.INP:

• Dòng đầu tiên ghi \(3\) số nguyên dương \(m, n, k\) (\(1 \le m, n \le 30\));
• Dòng thứ hai ghi số nguyên dương \(a_1, a_2, ..., a_m\) (các số không vượt quá \(1000\));
• Dòng thứ ba ghi số nguyên dương \(b_1, b_2, ..., b_n\) (các số không vượt quá \(1000\)).

Dữ liệu bảo đảm \(k\) không vượt quá số lượng phần tử của dãy phân số \(P\).

Output

Kết quả ra tệp văn bản PS.OUT:

• Một dòng duy nhất gồm \(2\) số nguyên dương là tử số và mẫu số của phân số tìm được (hai số ghi cách nhau một dấu cách).

Examples

2 3 2
10 30
20 30 60

1 3

1 6 5
1
6 3 5 3 1 10

1 1

Note

• \(50\%\) số test ứng với \(50\%\) số điểm của bài toán có \(m = 1\) và \(a_1 = 1\).

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2009 - 2010

Số Hexa là số biểu diễn trong hệ đếm \(16\), trong đó quy ước \(10\) là \(A\), \(11\) là \(B\), \(12\) là \(C\), \(13\) là \(D\), \(14\) là \(E\) và \(15\) là \(F\). Chẳng hạn số tự nhiên \(6747 = 1 × 16 + 10 × 16 + 5 × 16 + 11 × 16\) nên biểu diễn thành số Hexa là \(1A5B\). Viết liên tiếp các số tự nhiên \(1, 2, 3, ...\) thành dãy sau khi đã biểu diễn chúng dưới dạng số Hexa, ta được một dãy vô hạn các chữ số Hexa như sau:

\(123456789ABCDEF101112131415161718191A1B1C...\)

Yêu cầu: Cho trước một số nguyên dương \(n\) (\(1 \le n \le 10^9\)), tìm chữ số thứ \(n\) trong dãy trên.

Input

Dữ liệu vào từ tệp văn bản HEXA.INP:

• Gồm một dòng chứa số nguyên dương \(n\).
• Dữ liệu bảo đảm \(k\) không vượt quá số lượng phần tử của dãy phân số \(P\).

Output

Kết quả ra tệp văn bản HEXA.OUT:

• Chữ số thứ \(n\) tìm được.

Examples

10

A

16

1

Note

• \(50\%\) số test ứng với \(50\%\) số điểm của bài toán có \(n \le 30000\).

Nguồn: Học sinh Giỏi THPT Hà Nội năm 2009 - 2010

Biểu thức ngoặc là xâu chỉ gồm các ký tự \('('\) hoặc \(')'\). Biểu thức ngoặc đúng và bậc của biểu thức ngoặc được định nghĩa một cách đệ qui như sau:

• Biểu thức rỗng là biểu thức ngoặc đúng và có bậc bằng \(0\),
• Nếu \(A\) là biểu thức ngoặc đúng có bậc bằng \(k\) thì \((A)\) cũng là một biểu thức ngoặc đúng có bậc bằng \(k + 1\),
• Nếu \(A\) và \(B\) là hai biểu thức ngoặc đúng và có bậc tương ứng là \(k_1\) và \(k_2\) thì \(AB\) cũng là một biểu thức ngoặc đúng có bậc bằng \(max(k_1, k_2)\).

Ví dụ, \("()(())"\) là một biểu thức ngoặc đúng có bậc bằng \(2\) còn \("(()(()))"\) là một biểu thức ngoặc đúng và có bậc bằng \(3\).

Yêu cầu: Cho \(S\) là một xâu chỉ gồm các ký tự \('('\), \(')'\) và \('?'\), hãy tìm cách thay các ký tự \('?'\) thành ký tự \('('\) hoặc \(')'\) để nhận được xâu \(T\) là biểu thức ngoặc đúng và có bậc lớn nhất.

Input

Dữ liệu vào từ tệp văn bản BTN.INP:

• Gồm một dòng chứa xâu \(S\) (độ dài xâu \(S\) không vượt quá \(666\)) chỉ gồm các ký tự \('('\), \(')'\) và \('?'\).
• Dữ liệu bảo đảm bài toán luôn có nghiệm.

Output

Kết quả ra tệp văn bản BTN.OUT:

• Một dòng duy nhất là xâu \(T\) tìm được, nếu có nhiều xâu \(T\) thỏa mãn thì ghi xâu \(T\) có thứ tự từ điển ( \('(' < ')'\) ) lớn nhất.

Examples

(??((?)?

()((()))

????

(())

Note

• \(50\%\) số test ứng với \(50\%\) số điểm của bài toán có độ dài xâu \(S\) không vượt quá \(50\)