Killjee and Binary Strings

0

0 votes
Medium-Hard
Problem

Killjee likes binary strings and has 2 arrays A and B which consist of N binary strings. A binary string is a string consisting of only zeroes and ones, with no leading zeroes. These binary strings can be considered as numbers in base 2 and therefore, can be converted to numbers in base 10.

Rhezo has lost the arrays A and B that Killjee gave him. However, he has 2 other arrays C and D both of which consist of binary strings. Ci consists of a binary string which is the bitwise AND of Ai and Bi when considered as base 2 numbers. Di consists of a binary string which is the bitwise OR of Ai and Bi when considered as base 2 numbers.

Now, their friend Londs has Q queries which he wants both of them to answer. Queries are of 2 types. In the first type of query you will be given X,Y and Z. You need to replace Cx with Y and Dx with Z. In the second type of query, you will be given L and R. You need to find the following summation:

Ri=L(Ai+Bi)

Let the value of this summation be P. Now you need to insert all nodes from 1 to P in a trie. The process of insertion is as follows:

Create a node and name it as ROOT.

for all K from 1 to P:
    BITS[] = binary representation of K. /*most significant bit of K is present in BITS[0]*/
    LENGTH = number of bits in K.
    insert(ROOT,1)

void insert(NODE temp, int x) {
    if x >= LENGTH:
        return;
    if BITS[x] == 1:
        if temp does not have a right child:
            create right child of temp
        insert(right child of temp, x+1)
    else:
        if temp does not have a left child:
            create left child of temp
        insert(left child of temp, x+1)
}

For each query, you need to find the number of nodes ever created(in current query). As this value can be very large, print it modulo 109+7. If P is 0, print 0 as answer.

Rhezo and Killjee are very weak at programming and do not know how to answer these queries. Can you help them?

Input:

First line of input contains a single integer N denoting the number of binary strings in arrays C and D. Next line contains N space separated binary strings denoting Ci. Next line contains N space separated binary strings denoting Di.

Next line contains a single integer Q denoting the number of queries. Each of the next Q lines describe a query. If the first integer is 1, then it is a type 1 query. The next space separated integer is X, and the next two space separated binary strings are Y and Z.

If the first integer is 2, then it is a type 2 query and the next 2 space separated integers are L and R.

Output:

For each query of type 2, print the answer in a new line.

Constraints:

1N105

1Q104

1XN

1LRN

Y and Z are binary strings.

Length of any binary string 85

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

A can be {101, 11000, 1011}.

B can be {1000, 101, 11001}.

Editor Image

?