Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P184SUMF - ROUND 4F - Aki_Haru

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 (AL and AL+1 and … and AR) + (AL or AL+1 or … or AR).

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, Q1, Q2; 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 ≤ 105, 1 ≤ Q1, Q2 ≤ 4.105).

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

(Q1 + Q2) 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 < 230).
  • 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 Q2 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

Được gửi lên bởi:adm
Ngày:2018-07-27
Thời gian chạy:8s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.