This page is still under construction.

Parts of this page are still being built. What you see may change.

OR and Queries

Time limit1.5sMemory limit256 MB

Summary
Process range bitwise-OR updates on an array and count how many positions in a range currently equal a fixed K.
Level

Hard9 of 10

Topics
Segment tree, Bit manipulation, Implementation, Array
Solved
No attempts yet

Problem

You are given a sequence A1, A2, ..., AN of length N and a nonnegative integer K. Write a program that processes the following queries.

  • 1 l r x: for every l ≤ i ≤ r, replace Ai with Ai ∨ x, where ∨ is the bitwise OR operation.

  • 2 l r: print the number of indices l ≤ i ≤ r such that Ai = K.

The sequence is indexed starting from 1.

Input

The first line gives the length of the sequence N (1 ≤ N ≤ 250,000) and K (0 ≤ K < 230).

The second line gives A1, A2, ..., AN. (0 ≤ Ai < 230)

The third line gives the number of queries M (1 ≤ M ≤ 250,000).

The next M lines each contain one query. At least one query of type 2 is given. (1 ≤ l ≤ r ≤ N, 0 ≤ x < 230)

Output

For each query of type 2, print the answer on its own line.

Examples3

  1. Example 1

    Input
    5 3
1 2 3 4 5
3
2 1 5
1 1 3 2
2 1 5
    Expected output
    1
2

  2. Example 2

    Input
    7 7
7 4 2 5 7 5 4
5
2 1 7
1 2 4 7
2 1 7
1 6 7 3
2 1 7
    Expected output
    2
5
7

  3. Example 3

    Input
    6 5
4 2 1 5 3 1
7
2 1 3
2 1 6
1 5 6 4
2 1 6
2 3 5
1 1 6 8
2 1 6
    Expected output
    0
1
2
1
0