Cho số nguyên dương \(n\) và dãy số \(a_{1}, a_{2}, \ldots, a_{n}\).

Yêu cầu: Bạn hãy xác định xem liệu có tồn tại hai phần tử khác nhau sao cho tổng của chúng là số chẵn hay không. Nếu có bạn hãy in ra số chẵn lớn nhất có thể.

Hai phần tử \(a_{i}\) và \(a_{j}\) được gọi là khác nhau nếu \(i \neq j\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((2 \leq n \leq 10^{6})\).
• Dòng thứ hai chứa dãy số \(a_{1}, a_{2}, \ldots, a_{n}\) \((0 \leq a_{i} \leq 10^{9})\). Các số cách nhau một khoảng trắng.
• Dữ liệu vào đảm bảo rằng tất cả các phần tử trong dãy đều đôi một khác nhau.

Output

• In ra đáp án bài toán sau khi thực hiện yêu cầu đề bài. Nếu không tồn tại hai phần tử thỏa mãn yêu cầu đề bài hãy in ra \(-1\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 5000\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
2 3 4

6

shiba mới kí một đơn hàng làm đồ ăn đóng gói. Do số lượng khách hàng yêu cầu quá lớn, cậu ấy quyết định sẽ đi tìm đến _minhduc để nhờ anh ấy thiết kế một dây chuyền sản xuất.

Dây chuyền sản xuất bao gồm một số lượng nhất định máy tự động làm đồ ăn. Bằng độ thiên tài của mình, _minhduc có thể làm ra một chiếc máy mà có thể làm được tất cả các công việc, từ sơ chế, làm nóng, hút chân không, đóng gói để bảo quản sản phẩm, chiếc máy đều có thể làm được hết. Tuy nhiên để làm ra một chiếc máy như vậy, _minhduc cần thời gian là \(1\) ngày. Bên cạnh đó, để một chiếc máy có thể làm ra một sản phẩm đồ ăn đóng gói đạt yêu cầu, cũng cần \(1\) ngày.

Ban đầu trên dây chuyền không có máy. _minhduc cần làm đủ số lượng máy, sau đó shiba mới có thể vận hành. Thời gian để hoàn thành hợp đồng bằng thời gian mà _minhduc lắp ráp máy cộng với thời gian những chiếc máy làm ra số lượng sản phẩm đạt yêu cầu. Lưu ý thời gian những chiếc máy làm ra sản phẩm được làm tròn lên (ví dụ: \(\left \lceil \frac{4}{2} \right \rceil = 2, \left \lceil \frac{5}{2} \right \rceil = 3\)).

shiba thắc mắc, thời gian tối thiểu cần thiết để cậu ấy hoàn thành hợp đồng là bao lâu, bởi hạn chót của hợp đồng càng ngắn thì shiba có thể kiếm được càng nhiều tiền.

Input

• Dòng đầu chứa một số nguyên dương \(T\) \((T \leq 10^{5})\) - số lượng bộ test.
• \(T\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(n\) \((n \leq 10^{12})\) - số lượng sản phẩm.

Output

• Gồm \(T\) dòng, mỗi dòng chứa một số nguyên duy nhất là kết quả của mỗi bộ test.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(T, n \leq 100\).
• Subtask \(2\) (\(70\%\) số điểm): không có ràng buộc gì thêm.

Example

1
5

5

Cho số nguyên dương \(x\).

Yêu cầu: Bạn hãy đếm số bộ tứ \((a, b, c, d)\) thỏa mãn rằng \(a \times b + c \times d = x\) và \(a,b,c,d\) đều là số nguyên dương.

Input

• Chứa duy nhất số nguyên dương \(x\) \((2 \leq x \leq 10^{6})\).

Output

• In ra đáp án bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(2 \le x \le 50\).
• Subtask \(2\) (\(20\%\) số điểm): \(50 < x \le 200\).
• Subtask \(3\) (\(20\%\) số điểm): \(200 < x \le 5000\).
• Subtask \(4\) (\(20\%\) số điểm): \(5000 < x \le 2 \times 10^5\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

4

8

SW là một hacker mũ trắng. Công việc của cô ấy là phải xác định độ an toàn của một hệ thống, từ đó báo cáo lại cho người thuê cô ấy để nhận lương. Trong nhiệm vụ lần này, cô được mời tới hệ thống của sếp Flower_On_Stone. Hệ thống máy tính của sếp Flower_On_Stone bao gồm \(n\) máy tính. Trong hệ thống có \(m\) kết nối, một kết nối giữa hai máy tính \(u\) với \(v\) có nghĩa là máy tính \(v\) có thể bị điều khiển từ xa bởi máy tính \(u\). Ngay lập tức, hacker SW nhận ra sự nguy hiểm của hệ thống này, đó là từ một máy tính có thể truy cập tới nhiều máy tính khác.

Nếu máy tính \(u\) có thể điều khiển từ xa máy tính \(v\) và máy tính \(v\) có thể điều khiển từ xa máy tính \(x\), điều đó có nghĩa là máy tính \(u\) có thể điều khiển từ xa máy tính \(x\). SW quyết định tìm ra các máy tính có thể điều khiển nhiều máy tính khác nhiều nhất có thể, từ đó nâng cấp hệ thống bảo mật cho các máy tính này. Lưu ý là không tồn tại kết nối từ một máy tính tới chính nó.

Yêu cầu: Xác định số lượng máy tính nhiều nhất có thể bị điều khiển từ một máy tính bất kì, và có bao nhiêu máy tính như vậy?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n, m\) \((n \leq 10^{4}, m \leq 5 \times 10^{4})\) lần lượt là số máy tính và số kết nối.
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) \((1 \leq u, v \leq n)\) thể hiện có một kết nối giữa hai máy tính \(u\) và \(v\).

Output

• Dòng thứ nhất chứa hai số nguyên là số lượng máy tính nhiều nhất có thể bị điều khiển từ một máy tính bất kì và số lượng máy tính như vậy.
• Dòng thứ hai chứa các số nguyên tăng dần là các máy tính có thể điều khiển được nhiều máy tính nhất có thể.
• Lưu ý, một máy tính được tính là có thể được điều khiển được chính nó.

Example

5 4
1 3
2 3
3 4
3 5

4 2
1 2

Cho \(2\) mảng \(a\) và \(b\) gồm \(n\) phần tử gồm các số nguyên không âm và số nguyên dương \(k\).

Ở mỗi thao tác bạn có quyền chọn \(1\) số có giá trị \(i\) \((1 \leq i \leq n)\) sau đó hoán đổi giá trị \(a_{i}\) và \(b_{i}\).

Nhiệm vụ của bạn là tìm số thao tác nhỏ nhất để \(\sum_{i=1}^{n} a_{i}\) có giá trị bằng \(j\) (với \(j\) là các số tự nhiên từ \(1\) đến \(k\)).

Input

• Dòng đầu tiên gồm số \(n\) và \(k\) \((1 \leq n, k \leq 10^{5})\).
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(2\) số \(a_{i}\) và \(b_{i}\) \((1 \leq \sum_{i = 1}^{n} (a_{i} + b_{i}) \leq 2 \times 10^{5})\).

Output

• Gồm \(k\) dòng, dòng thứ \(j\) in ra số lượng thao tác ít nhất để \(\sum_{i=1}^{n} a_{i}\) có giá trị bằng \(j\), nếu không tồn tại cách nào thì in ra \(-1\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(1 \le n, k \le 2000, 1 \le \sum_{i =1}^{n} (a_{i} + b_{i}) \le 2000\).
• Subtask \(2\) (\(50\%\) số điểm): Không có rằng buộc gì thêm.

Example

3 5
1 3
2 5
0 7

-1
-1
0
-1
1

Có \(n\) ô vuông được đánh số từ \(1\) đến \(n\) từ trái sang phải. Ô vuông thứ \(i\) được đánh dấu bởi kí tự \(s_{i}\). Ban đầu tất cả các ô vuông mỗi ô vuông đều có một con robot.

_minhduc có thể đẩy các con robot ấy \(q\) lần.

Lần đẩy thứ \(i\) sẽ có hai kí tự lần lượt là \(t_{i}\) và \(d_{i}\), trong đó \(d_{i}\) là L hoặc R. Khi _minhduc đẩy robot, tất cả các con robot có đứng ở ô vuông có kí tự \(t_{i}\) sẽ bị đẩy sang trái nếu \(d_{i}\) là L, sẽ bị đẩy sang phải nếu \(d_{i}\) là R.

Tuy nhiên khi _minhduc đẩy các con robot đang đứng ở ô vuông thứ \(1\) sang trái hoặc đẩy các con robot đang đứng ở ô vuông thứ \(n\) sang phải thì các con robot đó đột nhiên biến mất.

Yêu Cầu: Bạn hãy đếm số con robot chưa bị biến mất sau khi _minhduc đẩy các con robot ấy \(q\) lần.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\) \((1 \leq n, q \leq 2 \times 10^{5})\).
• Dòng tiếp theo chứa chuỗi \(s\) \((\)độ dài của xâu không quá \(n\) và chỉ chứa chữ cái tiếng Anh in hoa\()\).
• Dòng tiếp theo chứa hai giá trị là \(t_{i}\) và \(d_{i}\) \((1 \leq i \leq q)\), mỗi bộ đôi giá trị cách nhau một dòng.
• \(t_{i}\) chỉ chứa chữ cái tiếng Anh in hoa và \(d_{i}\) chỉ tồn tại hai giá trị là L hoặc R.

Output

• In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): Có \(n, q \leq 100\).
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 4
ABC
A L
B L
B R
A R

2