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ố trong dãy đôi một khác nhau.

Output

• In ra số chẵn lớn nhất có thể tìm được từ tổng của hai phần tử bất kỳ trong dãy.
• Nếu không tồn tại, 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

Test 1

Input

3
2 3 4

Output

6

Note

• ~a_1 + a_2 = 2 + 3 = 5~

• ~a_1 + a_3 = 2 + 4 = 6~

• ~a_2 + a_3 = 3 + 4 = 7~

Vậy ~6~ là số chẵn lớn nhất thỏa mãn yêu cầu đề bài.

Dynos cần sản xuất ~n~ sản phẩm đồ ăn đóng gói bằng một dây chuyền máy tự động do Dynos thiết kế:

• Mỗi máy tự động mất 1 ngày để chế tạo.
• Khi có đủ máy, chúng mất 1 ngày để sản xuất 1 sản phẩm mỗi máy.
• Thời gian sản xuất được làm tròn lên khi số lượng sản phẩm không chia hết cho số máy.
• Ban đầu chưa có máy nào, Dynos cần chế tạo đủ số máy trước khi bắt đầu sản xuất.

Yêu cầu: Hãy tính thời gian tối thiểu cần thiết để sản xuất đủ ~n~ sản phẩm.

Input

• Dòng đầu chứa 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 cần sản xuất.

Output

• Gồm ~T~ dòng, mỗi dòng chứa một số nguyên duy nhất là thời gian tối thiểu cần thiết để sản xuất đủ ~n~ sản phẩm.

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

Test 1

Input

1
5

Output

5

Note

• Chế tạo 2 máy trong 2 ngày.
• Sản xuất ~\lceil \frac{5}{2} \rceil = 3~ ngày.
• Tổng thời gian: 2 + 3 = 5 ngày.

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 điều kiện: ~a \times b + c \times d = x~ với ~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 số lượng bộ tứ ~ (a, b, c, d) ~ thỏa mãn yêu cầu đề bài.

Scoring

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

Example

Test 1

Input

4

Output

8

Note

Các bộ tứ ~ (a, b, c, d) ~ thỏa mãn điều kiện là:

• ~(1, 1, 1, 3)~
• ~(1, 3, 1, 1)~
• ~(1, 1, 3, 1)~
• ~(3, 1, 1, 1)~
• ~(1, 2, 1, 2)~
• ~(1, 2, 2, 1)~
• ~(2, 1, 1, 2)~
• ~(2, 1, 2, 1)~

Cho ~2~ mảng ~a~ và ~b~ gồm ~n~ phần tử chứa các số nguyên không âm. Bạn có thể thực hiện hoán đổi phần tử giữa hai mảng theo vị trí tương ứng để tối ưu tổng của mảng ~a~.

Yêu cầu: Tìm số thao tác nhỏ nhất để tổng ~\sum_{i=1}^{n} a_{i}~ bằng ~j~ (với ~j~ từ ~1~ đến ~k~). Nếu không thể đạt được giá trị đó, in ra ~-1~.

Input

• Dòng đầu tiên gồm hai số nguyên ~n, k~ (~1 \leq n, k \leq 10^{5}~).
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_{i}, 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 thể đạt được giá trị đó thì in ra ~-1~.

Scoring

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

Example

Test 1

Input

3 5
1 3
2 5
0 7

Output

-1
-1
0
-1
1

Note

• Tổng ban đầu: ~a_1 + a_2 + a_3 = 1 + 2 + 0 = 3~.
• Giá trị cần đạt:
  • 1, 2, 4 không thể đạt → in ra -1.
  • 3 đã có sẵn → cần ~0~ thao tác.
  • 5 đạt được bằng cách hoán đổi a_3 và b_3 → cần ~1~ thao tác.

Có ~n~ ô vuông đánh số từ ~1~ đến ~n~ từ trái sang phải, mỗi ô có một con robot. Dynos có thể đẩy các robot ~q~ lần theo hướng trái L hoặc phải R.

• Lần đẩy thứ ~i~ có hai giá trị ~t_i~ và ~d_i~, trong đó:
  • Nếu ~d_i = L~, tất cả robot ở ô có ký tự ~t_i~ bị đẩy sang trái.
  • Nếu ~d_i = R~, tất cả robot ở ô có ký tự ~t_i~ bị đẩy sang phải.
• Nếu robot bị đẩy ra khỏi ranh giới (trái của ô 1 hoặc phải của ô n), nó biến mất.

Yêu cầu: Đếm số robot còn lại sau khi thực hiện ~q~ lần đẩy.

Input

• Dòng đầu chứa hai số nguyên dương ~n, q~ (~1 \leq n, q \leq 2 \times 10^{5}~).
• Dòng tiếp theo chứa chuỗi ~s~ (độ dài ~n~, chỉ chứa chữ cái in hoa ~A-Z~).
• ~q~ dòng tiếp theo, mỗi dòng chứa hai giá trị ~t_i~ và ~d_i~, trong đó:
  • ~t_i~ là một ký tự in hoa ~A-Z~.
  • ~d_i~ là L hoặc R.

Output

• In ra số robot còn lại sau ~q~ lần đẩy.

Scoring

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

Example

Test 1

Input

3 4
ABC
A L
B L
B R
A R

Output

2

Note

• Ban đầu, mỗi ô vuông có một robot.
• Lần đẩy 1: Ký tự A, hướng L → Robot ở ô 1 biến mất.
• Lần đẩy 2: Ký tự B, hướng L → Robot ở ô 2 bị đẩy sang ô 1.
• Lần đẩy 3: Ký tự B, hướng R → Không có robot nào ở ô 2, không thay đổi.
• Lần đẩy 4: Ký tự A, hướng R → Robot ở ô 1 bị đẩy sang ô 2.

Kết quả là còn lại 2 robot.