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

Cho số nguyên dương \(n\) (\(1 \le n \le 10^{18}\)).

Yêu cầu: Tìm số nguyên lớn nhất không vượt quá \(n\) và là tích của \(3\) số nguyên tố liên tiếp.

Input

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

• Dòng đầu tiên chứa số nguyên dương \(t\) tương ứng là số bộ test (\(1 \le t \le 15\));
• Trong \(t\) dòng tiếp theo mỗi dòng chứa số nguyên dương \(n\).

Output

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

• Gồm \(t\) dòng là kết quả của \(t\) bộ test tương ứng, nếu không tìm thấy số thỏa mãn ghi -1.

Example

1
36

30

Note

• \(30 = 2 \times 3 \times 5\)

Constraint

• \(50\%\) số test ứng với \(50\%\) số điểm của bài có \(n \le 10^6\)

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

Để thay đổi không khí sau những ngày làm việc căng thẳng, An dự định sẽ đi du lịch trong \(n\) ngày bằng xe riêng của mình. Ngày thứ \(i\), xe cần \(a_i\) lít xăng, (\(1 \le i \le n\)). Mỗi ngày An có thể mua số lượng xăng không hạn chế, nếu không dùng hết có thể để dành cho những ngày tiếp theo.

Yêu cầu: Hãy giúp An quyết định lượng xăng mua mỗi ngày để đáp ứng yêu cầu với tổng số tiền phải trả là ít nhất có thể.

Input

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

• Dòng đầu chứa số nguyên dương \(n\) (\(n \le 10^5\));
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) (\(a_i \le 10^5, 1 \le i \le n\));
• Dòng thứ ba chứa \(n\) số nguyên dương \(p_1, p_2, ..., p_n\) (\(p_i \le 10^5, 1 \le i \le n\)).

Output

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

• Một số nguyên duy nhất là tổng số tiền phải trả (tính bằng đồng) để mua xăng theo phương án tìm được.

Example

3
1 2 3
3000 1000 3000

8000

Note

• Ngày \(1\) mua \(1\) lít (\(3000\) đ), ngày \(2\) mua \(5\) lít (\(5000\) đ), ngày \(3\) mua \(0\) lít (\(0\) đ)

Constraint

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

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

Cho dãy gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\). Với mỗi dãy con \(a_l, a_{l+1}, \ldots, a_r\) (\(1 \le l \le r \le n\)), và số nguyên dương \(s\), gọi \(k_s\) là số lần xuất hiện của \(s\) trong dãy con \(a_l, a_{l+1}, \ldots, a_r\). Giá trị của dãy còn trên được tính bằng tổng của tất cả các tích \((k_s)^2 \times s\).

Ví dụ, cho dãy gồm \(8\) số nguyên dương \(1, 1, 2, 2, 1, 3, 1, 1\). Dãy con với \(l = 2, r = 7\) có \(k_1 = 3, k_2 = 2, k_3 = 1\) còn \(s > 3\) thì \(k_s = 0\). Từ đó giá trị của dãy con là \(3^2 \times 1 + 2^2 \times 2 + 1^2 \times 3 = 20\).

Yêu cầu: Cho \(t\) dãy con, hãy xác định giá trị của mỗi dãy.

Input

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

• Dòng đầu chứa hai số nguyên \(n\) và \(t\) (\(1 \le n \le 2 \times 10^5, 1 \le t \le 2 \times 10^5\));
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots,a_n\) (\(1 \le a_i \le 10^6\));
• Trong \(t\) dòng tiếp theo mỗi dòng chứa hai số nguyên \(l\) và \(r\) (\(1 \le l \le r \le n\)) mô tả một dãy con.

Output

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

• Gồm \(t\) dòng, dòng thứ \(k\) ghi một số nguyên là giá trị của dãy con thứ \(k\) \((1 \le k \le t)\).

Example

3 2
1 2 1
1 2
1 3

3
6

Note

• \(3 = 1^2 \times 1 + 1^2 \times 2\)
• \(6 = 2^2 \times 1 + 1^2 \times 2\)

Constraint

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

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

Trong một hội nghị quốc tế có \(m\) đại biểu tham dự được đánh số từ \(1\) đến \(m\). Tại hội nghị có sử dụng \(n\) ngôn ngữ khác nhau được đánh số từ \(1\) đến \(n\). Mỗi đại biểu biết một số ngôn ngữ trong \(n\) ngôn ngữ đó. Hai đại biểu \(u\) và \(v\) có thể trao đổi với nhau nếu biết một ngôn ngữ chung hoặc nhờ các đại biểu khác làm phiên dịch.

Khi một đại biểu \(u\) muốn chào đại biểu \(v\), đại biểu \(u\) sẽ nói to lời chào bằng một ngôn ngữ \(i\) mà đại biểu này biết và các đại biểu biết ngôn ngữ \(i\) đều hiểu được lời chào này. Nếu đại biểu \(v\) không hiểu lời chào đó (\(v\) không biết ngôn ngữ \(i\)), có một số đại biểu khác phiên dịch trung gian để đại biểu \(v\) hiểu được lời chào từ đại biểu \(u\). Gọi \(a_{uv}\) là số đại biểu có thể hiểu được lời chào của đại biểu \(u\) dành cho đại biểu \(v\).

Yêu cầu: Với mỗi cặp \(u, v\) (\(1 \le u \le m, 1 \le v \le m\)), xác định số dương \(a_{uv}\) nhỏ nhất.

Input

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

• Dòng đầu chứa hai số nguyên dương \(m\) và \(n\) (\(2 \le m \le 300, 1 \le n \le 300\));
• Trong \(m\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le m\)) chứa số nguyên dương \(k_i\) là số lượng các ngôn ngữ mà đại biểu \(i\) biết, tiếp theo là số \(k\), số hiệu các ngôn ngữ đó theo thứ tự tăng (\(1 \le k_i \le n\)).

Output

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

• Gồm \(m\) dòng và \(m\) cột. Tại vị trí dòng thứ \(u\), cột thứ \(v\) ghi số \(a_{uv}\) tìm được (\(1 \le u \le m, 1 \le v \le m\)). Trong đó \(a_{uu} = 0\). Nếu hai đại biểu \(u\) và \(v\) không thể hiểu lời chào của nhau thì \(a_{uv} = -1\).

Example

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

0 2 3 3
2 0 2 4
3 2 0 3
3 4 3 0

Note

• Đại biểu \(1\) chào đại biểu \(2\) bằng ngôn ngữ \(1\) có hai đại biểu hiểu lời chào là \(1\) và \(2\).
• Đại biểu \(1\) chào đại biểu \(2\) bằng ngôn ngữ \(3\). Sau đó đại biểu \(3\) phiên dịch sang ngôn ngữ \(2\) để đại biểu \(2\) hiểu được. Tất cả \(4\) đại biểu đều hiểu lời chào.
• Từ đó \(a_{12} = a_{21} = 2\).

Constraint

• \(50\%\) số test ứng với \(50\%\) số điểm của bài có \(2 \le m \le 100, 1 \le n \le 100\).