Cho mảng ~a~ gồm ~n~ số nguyên không âm. Đặt ~f(l, r) = a_l \text{ OR } a_{l+1} \text{ OR } ... \text{ OR } a_r~. Yêu cầu: Tính tổng ~\text{ XOR }~ mọi ~f(l, r)~ với (~1 \le l \le r \le n~).

Input: Nhập từ file "BIGBIRD.INP"

• Dòng đầu tiên chứa một số nguyên dương ~n~.
• Dòng thứ hai chứa n số nguyên không âm ~a_1, a_2,..., a_n~.

Output: Xuất ra file "BIGBIRD.OUT"

• Một số nguyên là giá trị cần tính.

Ví dụ

Input:

3
1 4 3

Output

3

Giải thích ví dụ:

~f(1, 1) \text{ XOR } f(1, 2) \text{ XOR } f(1, 3) \text{ XOR } f(2, 2) \text{ XOR } f(2, 3) \text{ XOR } f(3, 3)~ = ~1 \text{ XOR } 5 \text{ XOR } 7 \text{ XOR } 4 \text{ XOR } 7 \text{ XOR } 3~ = ~3~

Giới hạn

~0 \le a_i \le 1e9~

• Subtask 1 (25%): ~n \le 100~
• Subtask 2 (25%): ~n \le 1000~
• Subtask 3 (25%): ~a_i \le 1~
• Subtask 4 (25%): ~n \le 1e5~

Dãy ngoặc là một dãy chỉ gồm các kí tự mở ngoặc ( và đóng ngoặc ). Dãy ngoặc đúng là một dãy ngoặc được xây dựng dựa trên quy tắc sau:

• Dãy ngoặc rỗng là một dãy ngoặc đúng.
• Nếu ~A~ là một dãy ngoặc đúng thì ( ~A~ ) là một dãy ngoặc đúng.
• Nếu ~A~ và ~B~ là hai dãy ngoặc đúng thì ~AB~ cũng là dãy ngoặc đúng.

Ví dụ, (()), ()() và ()(()) là các dãy ngoặc đúng; còn )( hay (() thì không.

Bạn được cho một xâu kí tự ~s~ là một dãy ngoặc đúng cùng dãy ~q~ số ~p_1,p_2,...,p_q~. Bạn cần thực hiện ~q~ lượt thao tác. Tại thao tác thứ ~i~, bạn cần làm những việc sau:

• Thay đổi kí tự thứ ~p_i~ của ~s~ (từ ( sang ) hoặc ngược lại) thì xâu kí tự ~s~ trở thành dãy ngoặc đúng.
• In ra vị trí ~a_i~ vừa tìm được và thay đổi kí tự ở vị trí này.

Chú ý rằng, ở bất kì thao tác nào, bạn bắt đầu khi xâu ~s~ đang là dãy ngoặc đúng. Do đó, việc thay đổi kí tự thứ ~p_i~ khiến ~s~ bây giờ chắc chắn không phải dãy ngoặc đúng, và ta dễ dàng chứng minh được vị trí ~a_i~ cần tìm ở trên là luôn tồn tại. Khi thay đổi kí tự ở vị trí ~a_i~, ~s~ trở lại là dãy ngoặc đúng.

Input: Nhập từ file "DAYNGOAC.INP"

• Dòng đầu tiên chứa hai số nguyên dương ~n,q~ ~(1 \le n \le 10^6, 1 \le q \le 6 \times 10^5)~, lần lượt là độ dài của dãy ngoặc và số thao tác bạn cần thực hiện.
• Dòng thứ hai chứa xâu kí tự ~s~ là một dãy ngoặc đúng độ dài ~n~ .
• Dòng thứ ba chứa ~q~ số nguyên ~p_1,p_2,...,p_n~ ~(1 \le p_q \le n)~ mô tả các thao tác cần thực hiện.

Output: Xuất ra file "DAYNGOAC.OUT"

In ra ~q~ số nguyên ~a_1,a_2,...,a_n~ là các vị trí tìm được ở các thao tác. Các số cần được viết trên một dòng, ngăn cách với nhau bởi dấu cách.

Subtask

• Subtask ~1~ (~20\%~ số test): ~n \le 500, q \le 300~.
• Subtask ~2~ (~30\%~ số test): ~n \le 7000, q \le 4200~.
• Subtask ~3~ (~25\%~ số test): ~n \le 2 \times 10^5, q \le 10^5~.
• Subtask ~4~ (~25\%~ số test): ~n \le 10^6, q \le 6\times10^5~.

Ví dụ

Sample Input 1

6 3
((()))
4 3 1

Sample Output 1

2 2 1

Giải thích

Trong ví dụ trên, ban đầu dãy ngoặc ~s~ là ((())). Các thao tác diễn ra như sau:

• Thao tác đầu tiên: Sau khi thay đổi kí tự ở vị trí ~p_1 = 4~, ~s~ trở thành (((()), để ~s~ trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí ~a_1 = 2~. Khi đó ~s~ trở thành ()(()).
• Thao tác tiếp theo: Sau khi thay đổi kí tự ở vị trí ~p_2 = 3~, ~s~ trở thành ())()), để ~s~ trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí ~a_2 = 2~. Khi đó ~s~ trở thành (()()).
• Thao tác cuối cùng: Sau khi thay đổi kí tự ở vị trí ~p_3 = 1~, ~s~ trở thành )()()), để ~s~ trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí ~a_3 = 1~. Khi đó ~s~ trở thành (()()).

Bảo Bay Bổng được mời về làm việc cho cơ quan hàng không vũ trụ NASAR. Cơ quan này đang thực hiện một dự án khám phá hành tinh XYZ, nơi được cho là xuất hiện sự sống. Vì hành tinh XYZ rất lớn nên cơ quan này mới đi thám hiểm được một phần diện tích hình chữ nhật có kích thước ~m \times n~, với các hàng được đánh số từ ~1~ tới ~m~ và các cột được đánh số từ ~1~ tới ~n~.

Những khu vực ngoài hình chữ nhật này được coi là nguy hiểm và không được phép làm việc tại đó. Trong khu vực ~m \times n~ này, người ta đã chọn ra một số vị trí có toạ độ nguyên để xây dựng ~S~ trạm phát sóng và ~T~ trạm thu sóng phục vụ cho công việc nghiên cứu (ở cùng một toạ độ có thể đặt đồng thời nhiều trạm phát sóng và thu sóng). Vào thời điểm ~0~, các trạm phát sóng sẽ đồng loạt phát ra các nguồn sóng. Nếu ở thời điểm ~t~, sóng đang ở toạ độ ~(i, j)~ thì ở thời điểm ~t + 1~, sóng sẽ lan sang ~4~ ô kề cạnh với nó, cụ thể là ~(i - 1, j)~,~(i, j - 1)~,~(i + 1, j)~,~(i, j + 1)~. Thời điểm để một trạm thu sóng nhận được sóng là thời điểm nhỏ nhất sao cho có sóng từ một trạm phát sóng nào đó lan ra tới toạ độ trạm thu sóng này.

Hiện giờ, thời gian để tất cả các trạm thu sóng đều nhận được sóng là lâu hơn so với kế hoạch của NASAR cho nên họ muốn nhờ Bảo Bay Bổng công việc như sau: Hãy tìm cách đặt thêm một trạm phát sóng nữa sao cho thời gian để toàn bộ ~T~ thiết bị thu sóng đều nhận được sóng là nhỏ nhất có thể. Đồng thời, hãy đếm xem có bao nhiêu vị trí có thể đặt trạm phát sóng mới để đạt được thời gian đó.

Bảo Bay Bổng đã giải quyết hai vấn đề trên nhưng chưa chắc chắn về kết quả của mình. Bảo Bay Bổng muốn nhờ bạn tính toán lại để đối chiếu kết quả. Hãy giúp Bảo Bay Bổng hoàn thành công việc của NASAR giao cho.

Input: Nhập từ file "THUPHATSONG.INP"

• Dòng đầu tiên chứa hai số nguyên dương ~m, n~ ~(1 \le m, n \le 10^5)~.
• Dòng thứ hai chứa hai số nguyên không âm ~S, T~ ~(0 \le S \le 10^5, 1 \le T \le 10^5)~.
• ~S~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~x, y~ là toạ độ của các trạm phát sóng ~(1 \le x \le m, 1 \le y \le n)~.
• ~T~ dòng cuối cùng, mỗi dòng chứa hai số nguyên ~x, y~ là toạ độ của các trạm thu sóng ~(1 \le x \le m, 1 \le y \le n)~.

Output: Xuất ra file "THUPHATSONG.OUT"

In ra hai số nguyên cách nhau bởi một dấu cách:

• Số thứ nhất là thời gian nhỏ nhất để tất cả ~T~ trạm thu sóng nhận được sóng sau khi xây thêm trạm phát sóng thứ ~S + 1~.

• Số thứ hai là số lượng vị trí có thể đặt trạm phát sóng thứ ~S + 1~. Các vị trí này phải là các toạ độ nguyên nằm trong phạm vi hinh chữ nhật an toàn ~m \times n~ và giúp cho thời gian để toàn bộ ~T~ trạm thu sóng nhận được sóng là nhỏ nhất có thể.

Ví Dụ

Sample Input 1

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

Sample Output 1

1 4

Sample Input 2

2 3
0 1
1 1

Sample Output 2

0 1

Sample Input 3

2 3
1 1
1 2
1 2

Sample Output 3

0 6

Giải thích

• Hình ảnh minh hoạ cho ví dụ đầu tiên:

  • Các trạm thu sóng kí hiệu lần lượt là ~T_1, T_2, T_3, T_4~.

  • Trạm phát sóng thứ nhất kí hiệu là ~S_1~, phát ra sóng màu xanh lá cây.

  • Trạm phát sóng thứ hai kí hiệu là ~S_2~, phát ra sóng màu xanh da trời.

  • Trạm phát sóng được đặt thêm vào kí hiệu là ~S_3~, phát ra sóng màu vàng.

  • Dưới đây là hình ảnh của các trạm sóng khi chưa đặt thêm trạm phát sóng mới:

    

  • Khi chưa đặt thêm trạm phát sóng mới, các trạm thu sóng ~T_1, T_2, T_4~ nhận được sóng tại thời điểm ~1~. Trong khi đó, trạm ~T_3~ nhận được sóng tại thời điểm ~2~. Do đó, thời gian nhỏ nhất để tất cả các trạm đều nhận được sóng là thời điểm ~2~.

  • Dưới đây là hình ảnh của các cách đặt trạm sóng ~S_3~ để thời gian tất cả các trạm thu sóng nhận được sóng là nhỏ nhất có thể:

  

  • Bây giờ, tất cả các trạm thu sóng đều nhận được sóng tại thời điểm ~1~.

• Ở ví dụ thứ hai, việc đặt trạm phát sóng tại ~(1, 1)~ sẽ giúp cho trạm thu sóng nhận sóng ngay tại thời điểm ~0~.

• Ở ví dụ cuối cùng, bất kể đặt trạm phát sóng mới tại đâu, trạm thu sóng đều bắt được sóng ngay tại thời điểm ~0~ do đã có sẵn một trạm phát sóng đặt trùng toạ độ tại đó.

Giới hạn

• Subtask 1 (10%): ~m, n, S, T \le 50~
• Subtask 2 (20%): ~S = 0; m, n, T \le 500~
• Subtask 3 (30%): ~S = 0~
• Subtask 4 (20%): ~m, n, S, T \le 5000~
• Subtask 5 (20%): Không có ràng buộc gì thêm