Bạn được cho một dãy $a$ gồm $n$ số nguyên $a_1,a_2,\ldots,a_n$.
Ngoài ra, bạn được cho một tập $S$ gồm $q$ phép cập nhật. Mỗi phép cập nhật được xác định bởi ba số $l$, $r$ và $x$. Một phép cập nhật thực hiện phép toán xor với số $x$ lên tất cả các số trong đoạn $[l,r]$ của dãy $a$. Cụ thể, với mỗi $l \le i \le r$, thực hiện phép gán sau:
$$a_i := a_i \oplus x$$
Với một tập phép cập nhật $S$, định nghĩa $K(S)$ là tổng của $sum(i,j)^2$ trên mọi đoạn có thể có của dãy $a$ sau khi áp dụng tất cả các phép cập nhật trong tập $S$ lên dãy đã cho:
$$K(S)=\sum_{1 \le i \le j \le n}sum(i,j)^2$$
trong đó $sum(i,j)$ được định nghĩa là tổng các phần tử trong đoạn $[i,j]$:
$$sum(i,j)=\sum_{x=i}^{j}a_x$$
Nhiệm vụ của bạn là tìm tổng trên tất cả $2^q$ tập con của tập phép cập nhật $S$ đã cho. Cụ thể, nếu $P$ là tập hợp tất cả các tập con của tập $S$ gồm $q$ phép cập nhật, bạn phải tìm:
$$\sum_{subset \in P}K(subset)$$
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$ ($1 \le n \le 1000$) — số phần tử trong dãy.
Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$ cách nhau bởi dấu cách ($0 \le a_i < 128$ với mỗi $1 \le i \le n$) — dãy đã cho.
Dòng thứ ba chứa một số nguyên $q$ ($1 \le q \le 10^5$) — số phép cập nhật.
Mỗi dòng trong $q$ dòng tiếp theo chứa ba số nguyên $l$, $r$ và $x$ cách nhau bởi dấu cách ($1 \le l \le r \le n$, $0 \le x < 128$) — mô tả các phép cập nhật.
Dữ liệu ra
In một số nguyên — đáp án của bài toán. Vì đáp án có thể rất lớn, hãy in phần dư của nó khi chia cho $10^9+7$.
Nhiệm vụ con
Bài toán gồm chín nhiệm vụ con:
- $1 \le n \le 10$, $1 \le q \le 10$, $0 \le a_i,x < 128$ với mọi $1 \le i \le n$. Được 4 điểm.
- $1 \le n \le 100$, $1 \le q \le 10$, $0 \le a_i,x < 128$ với mọi $1 \le i \le n$. Được 5 điểm.
- $1 \le n \le 100$, $1 \le q \le 100000$, $0 \le a_i,x < 32$ với mọi $1 \le i \le n$. Đảm bảo rằng độ dài của mọi đoạn cập nhật đều bằng $1$. Được 6 điểm.
- $1 \le n \le 1000$, $1 \le q \le 500$, $0 \le a_i,x < 128$ với mọi $1 \le i \le n$. Đảm bảo rằng mọi đoạn cập nhật đôi một không giao nhau. Được 9 điểm.
- $1 \le n \le 30$, $1 \le q \le 20$, $0 \le a_i,x < 32$ với mọi $1 \le i \le n$. Được 8 điểm.
- $1 \le n \le 30$, $1 \le q \le 5000$, $0 \le a_i,x < 32$ với mọi $1 \le i \le n$. Được 11 điểm.
- $1 \le n \le 300$, $1 \le q \le 300$, $0 \le a_i,x < 128$ với mọi $1 \le i \le n$. Được 19 điểm.
- $1 \le n \le 500$, $1 \le q \le 100000$, $0 \le a_i,x < 128$ với mọi $1 \le i \le n$. Được 30 điểm.
- $1 \le n \le 1000$, $1 \le q \le 100000$, $0 \le a_i,x < 128$ với mọi $1 \le i \le n$. Được 8 điểm.
Ví dụ
Dữ liệu vào 1
2 1 3 1 1 2 2
Dữ liệu ra 1
52
Dữ liệu vào 2
5 1 2 3 4 5 0
Dữ liệu ra 2
1001
Ghi chú
Phép toán xor là phép HOẶC loại trừ theo bit.
Trong ví dụ thứ nhất, có $2^1=2$ dãy có thể có sau khi áp dụng các phép cập nhật — có áp dụng phép cập nhật duy nhất đã cho và không áp dụng. Ở cả hai dãy, tổng thu được đều bằng $26$.
Trong ví dụ thứ hai, tập $S$ rỗng, tập hợp tất cả các tập con chỉ gồm một phần tử $\varnothing$ — tập rỗng, nghĩa là không có phép cập nhật nào và bạn phải tìm $K(\varnothing)$ cho dãy $a$ đã cho.