Tuệ Minh có một mảng ~a_1, a_2, \dots, a_n~ gồm ~n~ số nguyên và hai số nguyên không âm ~x, y~. Cô ấy cần thực hiện ~m~ truy vấn thuộc hai loại sau:

• ~1~ ~l~ ~r~ ~c~: thực hiện phép gán ~a_i = c~ với mọi ~i~ thỏa mãn ~(l \le i \le r)~, tức là thay các phần tử từ ~l~ đến ~r~ bằng giá trị ~c~.

• ~2~ ~l~ ~r~: tìm số lượng cặp ~(L, R)~ thỏa mãn ~l \le L \le R \le r~ và phép OR bitwise của tất cả các phần tử trong đoạn ~[L, R]~ nằm trong đoạn ~[x, y]~ (lưu ý rằng ~x, y~ là hằng số cố định cho tất cả các truy vấn).

Hãy giúp Tuệ Minh thực hiện tất cả các truy vấn đã cho!

Giải thích về phép OR bitwise: Phép OR bitwise được định nghĩa trên cặp số nguyên không âm. Để tính, ta viết cả hai số ở dạng nhị phân. Kết quả là một số nhị phân mà tại mỗi vị trí bit, nếu có ít nhất một số có bit bằng ~1~ thì kết quả tại vị trí đó là ~1~.

Ví dụ: ~10_{10} \mathbin{\mathrm{OR}} 19_{10} = 1010_2 \mathbin{\mathrm{OR}} 10011_2 = 11011_2 = 27~.

Input

• Dòng đầu chứa bốn số nguyên ~n, m, x, y~ ~(1 \le n, m \le 3 \cdot 10^4; 0 \le x \le y < 2^{20})~ — số phần tử, số truy vấn và hai hằng số ~x, y~.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(0 \le a_i < 2^{20})~.

• ~m~ dòng tiếp theo mô tả các truy vấn, có ~2~ dạng:

  • ~1~ ~l~ ~r~ ~c~ ~(1 \le l \le r \le n; 0 \le c < 2^{20})~: ~a_i = c~ với ~(l \le i \le r)~.

  • ~2~ ~l~ ~r~ ~(1 \le l \le r \le n)~: tìm số lượng đoạn con ~[L, R]~ với ~l \le L \le R \le r~ sao cho OR của tất cả các phần tử trong đoạn ~a_L \dots a_R~ nằm trong đoạn ~[x, y]~.

Output

Với mỗi truy vấn loại ~2~, in ra số lượng đoạn con thỏa mãn điều kiện, mỗi số trên một dòng.

Sample Input 1

4 8 7 11
0 3 6 1
2 1 4
2 3 4
1 1 4 7
2 1 4
2 1 3
2 1 1
1 3 4 0
2 1 4

Sample Output 1

5
1
10
6
1
7