Một bảng hình chữ nhật kích thước ~m \times n~ ô, được chia thành các ô vuông ~1 \times 1~ gồm ~m~ hàng và ~n~ cột. Hàng được đánh số từ ~1~ tới ~m~ (từ trên xuống dưới), cột được đánh số từ ~1~ tới ~n~ (từ trái qua phải).

Một quả bóng bắt đầu ở ô ~[x, y]~ và di chuyển theo đường chéo với hướng ban đầu là phải trên (tức là từ ~[i, j]~ sang ~[i-1, j+1]~).

Quy tắc phản xạ:

• Khi quả bóng chạm vào một cạnh của bảng, nó sẽ đổi hướng sang một hướng vuông góc với hướng cũ (và hướng mới được chọn sao cho quả bóng tiếp tục đi vào trong bảng).
• Nếu ô mà quả bóng đi tới theo hướng cũ là một trong 4 ô góc của bảng, thì hướng mới sẽ là ngược lại với hướng cũ.
• Trò chơi kết thúc khi quả bóng quay trở lại đúng ô xuất phát ~[x, y]~.

Ví dụ:

Yêu cầu

Cho ~m, n, x, y~. Hãy tính số lần đổi hướng (phản xạ) ít nhất để quả bóng trở lại ô ban đầu ~[x, y]~. Nếu quả bóng không thể trở lại ô ban đầu, in ra ~-1~.

Dữ liệu

Một dòng duy nhất chứa ~4~ số nguyên dương ~m, n, x, y~ với ràng buộc: ~1 < x < m < 10^7, ; y < n < 10^7~.

Kết quả

In ra một số nguyên:

• Số lần phản xạ ít nhất trước khi quả bóng trở lại ~[x, y]~;
• Hoặc ~-1~ nếu không thể trở lại.

Ví dụ

Ví dụ 1

Input

9 4 8 3

Output

5

Ví dụ 2

Input

9 5 4 4

Output

6

Giải thích

Ví dụ 1

Với ~m=9, n=4, x=8, y=3~, sau khi quả bóng chạm các cạnh theo đúng quy tắc và đổi hướng tổng cộng ~5~ lần, nó trở lại ô ~[8, 3]~ lần đầu tiên.

Ví dụ 2

Với ~m=9, n=5, x=4, y=4~, quả bóng cần ~6~ lần phản xạ để quay lại ô ~[4, 4]~.

Ràng buộc và chấm điểm

Ràng buộc

• Một dòng gồm ~m, n, x, y~ với: ~1 < x < m < 10^7, ; y < n < 10^7~.

Chấm điểm

• ~50%~ số test có ~m, n \le 100~.
• ~50%~ số test còn lại không có ràng buộc gì thêm.

Cho hai dãy ~a~ và ~b~ có cùng độ dài ~n~, mỗi phần tử chỉ nhận giá trị trong tập ~{1,2}~.

Ta được phép thực hiện hai loại thao tác sau để thay đổi các dãy:

• Thao tác loại 1: Chọn hai chỉ số ~i, j~ với ~1 \le i, j \le n~, hoán đổi giá trị của ~a_i~ và ~b_j~.
• Thao tác loại 2: Chọn hai chỉ số ~i, j~ với ~1 \le i \ne j \le n~, hoán đổi giá trị của ~b_i~ và ~b_j~.

Yêu cầu

Hãy biến đổi để hai dãy trở thành giống hệt nhau (tức là ~a_k = b_k~ với mọi ~k~), sao cho:

1. Tổng số thao tác là ít nhất có thể.
2. Trong các phương án có tổng số thao tác ít nhất, hãy chọn phương án có số thao tác loại 1 là ít nhất.

Nếu không thể biến đổi để hai dãy giống nhau, hãy báo không thể.

Dữ liệu

• Dòng 1: số nguyên dương ~n~ (~1 \le n \le 10^6~).
• Dòng 2: ~n~ số nguyên ~a_i~ (~1 \le a_i \le 2~).
• Dòng 3: ~n~ số nguyên ~b_i~ (~1 \le b_i \le 2~).

Kết quả

• Nếu không thể biến đổi để ~a = b~, in ra ~-1~.

• Nếu có thể, in ra trên một dòng hai số nguyên:

  • ~T~: tổng số thao tác ít nhất,
  • ~K~: số thao tác loại ~1~ ít nhất trong các phương án đạt ~T~.

Ví dụ

Ví dụ 1

Input

7
1 2 2 2 1 2 2
2 1 1 2 2 1 1

Output

3 1

Ví dụ 2

Input

6
1 2 1 2 1 2
2 1 2 1 2 1

Output

3 0

Ví dụ 3

Input

4
1 1 2 1
2 1 1 2

Output

-1

Giải thích

Ví dụ 1

Một cách đạt ~3~ thao tác với đúng ~1~ thao tác loại ~1~:

• Loại ~1~: đổi ~a_2~ với ~b_3~
• Loại ~2~: đổi ~b_1~ với ~b_6~
• Loại ~2~: đổi ~b_5~ với ~b_7~ Sau đó thu được ~a = b = (1,1,2,2,1,2,2)~.

Ví dụ 2

Có thể chỉ dùng thao tác loại ~2~ để hoán vị dãy ~b~ cho trùng với ~a~, cần tối thiểu ~3~ lần, ví dụ đổi các cặp vị trí ~ (1,2)~, ~(3,4)~, ~(5,6)~ trong ~b~.

Ví dụ 3

Tổng số phần tử bằng ~1~ trong hai dãy là ~5~ (lẻ), nên không thể biến đổi để hai dãy cuối cùng giống hệt nhau.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 10^6~
• ~1 \le a_i \le 2~
• ~1 \le b_i \le 2~

Chấm điểm

• Subtask 1 (30%): ~n \le 10~
• Subtask 2 (70%): không có ràng buộc gì thêm

Cho chuỗi ký tự ~s~ có độ dài ~n~, chỉ gồm các chữ cái tiếng Anh viết thường. Cho trước hệ số cân bằng ~x~ và số lần thay đổi tối đa ~k~. Mỗi thao tác thay đổi cho phép đổi một ký tự bất kỳ trong ~s~ thành một ký tự khác.

Một chuỗi được gọi là cân bằng hệ số ~x~ nếu đó là một chuỗi ký tự liên tiếp có đúng ~x~ loại ký tự khác nhau, và mỗi loại xuất hiện cùng số lần.

Yêu cầu

Hãy tìm độ dài lớn nhất của một chuỗi con liên tiếp của ~s~ có thể trở thành chuỗi cân bằng hệ số ~x~ sau nhiều nhất ~k~ thao tác thay đổi.

Dữ liệu

• Dòng đầu tiên chứa ba số nguyên ~n~, ~x~, ~k~ với ~1 \le x \le 26~, ~0 \le k \le n~.
• Dòng thứ hai chứa chuỗi ~s~ có độ dài ~n~.

Kết quả

• Một số nguyên duy nhất là độ dài lớn nhất của chuỗi con thỏa mãn. Nếu không tồn tại chuỗi con nào thỏa mãn, in ra ~-1~.

Ví dụ

Ví dụ 1

Input

7 3 1
aaaabbc

Output

6

Ví dụ 2

Input

7 3 0
abaabac

Output

3

Ví dụ 3

Input

6 4 1
daaaba

Output

-1

Giải thích

Ví dụ 1

Xét chuỗi con ~aaabbc~ có độ dài ~6~. Tần suất các ký tự là ~a:3~, ~b:2~, ~c:1~. Chỉ cần đổi một ký tự ~a~ thành ~c~ thì thu được tần suất ~2,2,2~, nên đây là một chuỗi cân bằng hệ số ~3~. Không thể đạt độ dài ~7~ vì ~7~ không chia hết cho ~3~.

Ví dụ 2

Vì ~k = 0~, chuỗi con được chọn phải vốn đã là chuỗi cân bằng. Chuỗi con ~bac~ có đúng ~3~ ký tự khác nhau, mỗi ký tự xuất hiện ~1~ lần, nên đáp án là ~3~.

Ví dụ 3

Với ~x = 4~, độ dài chuỗi cân bằng phải là bội của ~4~. Chuỗi con độ dài ~4~ bất kỳ muốn trở thành cân bằng thì phải có ~4~ ký tự khác nhau, mỗi ký tự xuất hiện đúng ~1~ lần. Trong ví dụ này, không có chuỗi con nào có thể đạt được điều đó chỉ với nhiều nhất ~1~ phép đổi, nên kết quả là ~-1~.

Ràng buộc

• Có ~30\%~ số test có ~x = 1~, ~n \le 10^5~.
• Có ~30\%~ số test có ~n \le 1000~.
• ~40\%~ số test còn lại có ~k = 0~, ~n \le 10^5~ và chuỗi ~s~ có đúng ~x~ loại ký tự đầu tiên trong bảng chữ cái. Ví dụ, nếu ~x = 4~ thì ~s~ chỉ chứa các ký tự thuộc tập ~{a, b, c, d}~.

Xét cây phân đoạn xây trên dãy gồm ~n~ phần tử, được đánh số đỉnh như sau:

• Đỉnh gốc có chỉ số ~1~ và quản lý đoạn ~[1, n]~.
• Mỗi đỉnh có chỉ số ~x~ quản lý một đoạn liên tiếp ~[l, r]~ với độ dài ~len = r - l + 1~.
• Nếu ~len = 1~ thì đỉnh đó là lá.

• Nếu ~len > 1~ thì đỉnh đó có đúng ~2~ con:

  • Con trái có chỉ số ~2x~, quản lý đoạn bên trái có độ dài ~\left\lceil \dfrac{len}{2} \right\rceil~.
  • Con phải có chỉ số ~2x + 1~, quản lý đoạn bên phải có độ dài ~\left\lfloor \dfrac{len}{2} \right\rfloor~.

Gọi ~maxNode~ là chỉ số lớn nhất xuất hiện trong cây phân đoạn.

Yêu cầu

Cho ~q~ truy vấn. Với mỗi truy vấn, biết số phần tử ~n~, hãy xác định giá trị ~maxNode~ của cây phân đoạn tương ứng.

Dữ liệu

• Dòng đầu chứa số nguyên dương ~q~ là số truy vấn, thỏa mãn ~q \le 10^5~.
• Dòng thứ hai chứa ~q~ số nguyên dương ~n_1, n_2, \dots, n_q~, trong đó ~1 \le n_i \le 10^{18}~.

Kết quả

In ra một dòng gồm ~q~ số nguyên, số thứ ~i~ là giá trị ~maxNode~ ứng với truy vấn ~n_i~. Các số cách nhau bởi ít nhất một dấu cách.

Ví dụ

Ví dụ 1

Input

4
6 7 9 10

Output

13 13 17 25

Minh họa

Giải thích

Ví dụ 1

• Với ~n = 6~, cây phân đoạn thu được có chỉ số lớn nhất là ~13~.
• Với ~n = 7~, cây phân đoạn thu được có chỉ số lớn nhất là ~13~.
• Với ~n = 9~, cây phân đoạn thu được có chỉ số lớn nhất là ~17~.
• Với ~n = 10~, cây phân đoạn thu được có chỉ số lớn nhất là ~25~.

Ràng buộc và chấm điểm

Ràng buộc

• ~q \le 10^5~
• ~1 \le n_i \le 10^{18}~

Chấm điểm

• Subtask ~1~: ~50%~ số test có ~n_i \le 10^6~.
• Subtask ~2~: ~50%~ số test còn lại không có ràng buộc gì thêm.