Problem of the Week 2

Kết nối chơi game

Time limit: 1.0s / Memory limit: 512M

Points: 100

Có ~N~ học sinh và ~M~ trò chơi vi tính. Mỗi học sinh chỉ thích chơi một trò duy nhất và mỗi trò chơi có ít nhất một học sinh thích. Nhà trường tổ chức kết nối mạng LAN cho các máy trong ~Q~ phút, phút thứ ~i~ nối ~2~ máy của học sinh ~U_i~ và ~V_i~ (coi như đồ thị vô hướng). Tất cả những học sinh thích chơi cùng một loại game sẽ bắt đầu chơi khi máy tính của họ liên thông (có thể đi qua các đỉnh chứa game khác). Hỏi thời gian bắt đầu chơi của mỗi game.

Nếu game chỉ có ~1~ người thích thì sẽ bắt đầu vào phút thứ ~0~

Nếu ~1~ loại game không thế liên thông sau ~Q~ phút thì in ra ~-1~ ứng với game đó

Input

Dòng ~1~: ~N~, ~M~, ~Q~ tương ứng với số học sinh, số trò chơi, số phút (mỗi phút nối ~1~ dây LAN)

Dòng ~2~: Gồm ~N~ số ~A_{i}~ miêu tả trò chơi mà học sinh thứ ~i~ thích

~Q~ dòng tiếp theo: mỗi dòng gồm ~2~ số ~U_{i}~ và ~V_{i}~

Output

Gồm ~M~ dòng, dòng thứ ~i~ là thời điểm bắt đầu chơi của game thứ ~i~

Giới hạn

~1 \le N~, ~M \le 10^{5}~.
~0 \le Q \le 10^{5}~

Sample Input

Sample Output

3
4

Trò chơi của VOVA

Submit

Time limit: 6.0s / Memory limit: 512M

Points: 100

Đây là trò chơi một người tạm gọi là bạn Vova với hai dãy số nguyên dương: ~a~ gồm ~n > 1~ phần tử và ~b~ gồm ~m > 1~ phần tử. Vova phải thực hiện các thao tác sau đây:

Chia mỗi dãy ~a~ và ~b~ thành ~k > 0~ nhóm, mỗi nhóm gồm dãy các phần tử đứng liền nhau, số phần tử của mỗi nhóm có thể khác nhau nhưng tối thiểu phải là ~1~. Số ~k~ do Vova tự quyết định; Mã số các nhóm là ~1~, ~2~, ~\ldots~, ~k~;
Với mỗi nhóm ~i~ trong dãy ~a~ Vova phải tính tổng ~c~ = ~c_{1} + c_{2} + \ldots + c_{k}~.

trong đó:

~c_{i} = (s_{i} - u_{i})(t_{i} - v_{i})~, ~i~ = ~1~, ~2~, ~\ldots~, ~k~;
~s_{i}~ là tổng các phần tử của nhóm ~i~ trong dãy a;
~u_{i}~ là số phần tử của nhóm ~i~ trong dãy a;
~t_i~ là tổng các phần tử của nhóm ~i~ trong dãy b;
~v_{i}~ là số phần tử của nhóm ~i~ trong dãy b.

Hãy cho biết giá trị nhỏ nhất có thể đạt được của ~c~

Input

Dòng đầu tiên chứa ~2~ số ~n~ và ~m~ (~1 \le n, m \le 10^4~)

Dòng thứ hai chứa ~n~ phần tử của dãy a (~1 \le a_i \le 10^5~).

Dòng thứ ba chứa ~m~ phần tử của dãy b (~1 \le b_i \le 10^5~).

Output

Chứa giá trị nhỏ nhất có thể đạt được của ~c~.

Sample Input

3 2
3 7 4
5 2

Sample Output

Trò chơi nén số (Reworked)

Submit

Time limit: 1.0s / Memory limit: 256M

Points: 100

Exile_2k4 có số nguyên dương ~N~. Cậu sẽ chơi một trò chơi nhỏ với con số này.

Đầu tiên, cậu sẽ viết tất cả các số từ ~1~ đến ~N~ thành một xâu liên tiếp ~S_N = 12345678910111213 \dots~ Sau đó, cậu sẽ nén các xâu con có các chữ số giống nhau của xâu ~S~ này thành về ~1~ chữ số duy nhất.

Lấy ví dụ về việc nén xâu con, với ~N = 12~ ta có xâu ~S_{12} = 123456789101112~ thì sau khi nén, ta có ~S_{12} = 1234567891012~ có độ dài là ~M = 13~. Như vậy, ta dễ thấy là ~2~ chữ số liên tiếp nhau của ~S~ sau khi nén luôn khác nhau.

Bây giờ Exile_2k4 đố bạn một câu hỏi ngược. Cậu ta sẽ cho bạn số ~M~, và nhiệm vụ của bạn là tìm số ~K~ lớn nhất sao cho độ dài của xâu ~S_K~ sau khi nén không vượt quá ~M~.

Dễ chứng minh được là độ dài của xâu ~S_K~ sau khi nén là duy nhất với mỗi ~K~.