Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Một chàng trai phong trần và một cô nàng dịu dàng, xinh đẹp nhưng cũng đầy sắc sảo; thật không ngoa khi nói Aki và Haru là một cặp thanh mai trúc mã của Hội đồng (tiếc là họ không phải một đôi :> ). Mà thực sự, họ vốn luôn hoạt động như một đôi, cùng nhau đi qua hàng loạt các chiến dịch.

Một lần, hai người thực hiện việc hack một hệ thống dữ liệu. Như thường lệ, Haru đi tiên phong và đã thu được toàn bộ thông tin cần biết. Việc truy cập thì sẽ là phần của Aki.

Nhưng lần này, mọi thứ có vẻ không đơn giản.

Có vẻ như chủ sở hữu hệ thống này là một người rất thích đùa. Hệ thống bảo mật của hắn gồm một mảng số (mà Haru đã khai thác được ra trước đó), và luôn biến đổi vào những thời điểm ngẫu nhiên. Xen giữa thời gian đó, lần lượt các câu hỏi được đưa ra để hỏi người truy cập, nếu trả lời đúng đủ số lần thì hệ thống mới mở.

Tổng quát hơn, cho một mảng số A[] kích thước N.

Có hai loại hành động có thể diễn ra:

Hành động 1: Một phần tử ở vị trí thứ X sẽ thay đổi giá trị về Z.

Hành động 2: Hệ thống đặt ra cho máy trạm 1 câu hỏi gồm hai số L, R (1 ≤ L ≤ R ≤ N). Với câu hỏi đó, máy trạm phải trả lời giá trị của phép tính (A_L and A_L+1 and … and A_R) + (A_L or A_L+1 or … or A_R).

Cho dù đã dành tới 16 năm cuộc đời tu luyện các phép xử lý bit, với lượng dữ liệu lớn thì Aki vẫn có thể gặp khó khăn. Vậy nên, Haru lại cùng Aki sát cánh giải quyết vấn đề này, và họ đã thành công.

Còn bạn thì sao? Bạn có tự tin vào khả năng của mình không?

Nếu có, và thành công, Haru-chan sẽ có một món quà đặc biệt cho bạn! <3

Input

Dòng đầu tiên chứa ba số nguyên N, Q₁, Q₂; lần lượt là kích thước mảng A[], số hành động thay đổi phần tử, số hành động đặt câu hỏi của hệ thống (1 ≤ N ≤ 10⁵, 1 ≤ Q₁, Q₂ ≤ 4.10⁵).

Dòng thứ hai chứa N số nguyên là các phần tử A_i (0 ≤ A_i < 2³⁰).

(Q₁ + Q₂) dòng tiếp theo thể hiện tất cả các hành động theo thứ tự thời gian, có dạng như sau:

• Bắt đầu bằng một số nguyên T: T = 1 nếu là hành động thay đổi, T = 2 nếu là hành động đặt câu hỏi.
• Nếu T = 1, tiếp trên dòng đó là 2 số nguyên X, Z; thể hiện phép gán A_X := Z (1 ≤ X ≤ N, 0 ≤ Z < 2³⁰).
• Nếu T = 2, tiếp trên dòng đó là 2 số nguyên L, R (1 ≤ L ≤ R ≤ N).

Nhớ rằng, không có ràng buộc nào về thứ tự các hành động. Tức là, một hành động gán có thể xuất hiện cuối cùng, hay một hành động hỏi xuất hiện ngay đầu tiên, tương tự với tất cả các khả năng khác.

Output

Output gồm Q₂ dòng, mỗi dòng là trả lời cho mỗi câu hỏi do hệ thống đặt ra, thứ tự trả lời đúng với thứ tự xuất hiện câu hỏi.

Example

Input:
4 1 3
5 9 2 6
2 2 3
1 3 4
2 2 3
2 3 4

Output:
11
13
10