| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P146SUMD - ROUND 6D - Kiểm tra bài tập |
Tèo đang học về các phép toán bit, thế là thầy giáo của cậu bắt cậu thực hiện đi thực hiện lại việc tính với các phép toán đó. Thầy giao cho cậu một dãy có 2^n số, lượt đầu tiên, cậu lần lượt thực hiện phép toán or giữa 2 phần tử cạnh nhau, sau lượt này cậu còn 2 ^ (n-1) phần tử. Lượt 2, cậu lại tiếp tục làm như vậy nhưng lần này phép toán mà cậu dùng là xor. Cứ tiếp tục như vậy cho đến khi dãy số còn đúng một phần tử duy nhất. Giá trị của phần tử cuối cùng đó gọi là kết quả của dãy số.
Ví dụ: Dãy số ban đầu là a = (1, 2, 3, 4).
Sau lượt 1 ta được : (3, 7) ( 1 or 2 = 3, 3 or 4 = 7)
Sau lượt 2 ta được : (4) ( 3 xor 7 = 4)
Vậy kết quả dãy số là 4.
Để tránh việc Tèo đi hỏi bạn để làm bài đó. Thầy giáo mới kiểm tra Tèo bằng cách như sau, thầy thay đổi một số trong dãy số đang có và bắt Tèo tính kết quả của dãy số đó. Thầy kiểm tra Tèo nhiều lần như vậy để Tèo không có khả năng đi hỏi bài bạn khác.
Thầy soạn xong đề và các test để kiểm tra rồi tuy nhiên công việc chiếm nhiều thời gian, thầy nhờ các bạn giúp thầy tính kết quả của dãy số đấy !
Input
Dòng đầu tiên gồm 2 số nguyên n và m (1 <=n <= 17, 1 <=m <= 10^5).
Dòng tiếp theo chứa 2^n phần tử của dãy số số a[] (0 <= a[i] < 2^30, 1 <=i <= 2^n).
m dòng sau, mỗi dòng gồm 2 số nguyên p và b, đại diện cho test kiểm tra của thầy, thay số a[p] = b. Các test kiểm tra được thực hiện lần lượt từ trên xuống (1 <= p <= 2^n, 0 <= b < 2^30).
Output
m dòng mỗi dòng là kết quả của mỗi lần test.
Example
Input:
2 4
1 6 3 5
1 4
3 4
1 2
1 2
Output:
1
3
3
3
| Được gửi lên bởi: | adm |
| Ngày: | 2014-07-31 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 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 |
