Binary String Queries

You are given n binary strings and q queries. There are two types of queries:

• Type 1: For a query 1 l r, compute the bitwise AND (using binary representation) of all binary strings from index l to r (inclusive). Formally, if the binary string at position i is represented as an integer a_i, then the answer is \(a_l \& a_{l+1} \& \cdots \& a_r\).
• Type 2: For a query 2 l r, increment each binary string from index l to r by 1. The binary strings are maintained in a fixed-width format. When the addition causes the binary representation to exceed its fixed width, drop the most significant bit so that the string remains the same length. For example, if the original binary string was of length \(m\), the new string is computed as follows: let \(x\) be the integer value of the string, then compute \(x+1\) and convert it to binary. If the binary representation has more than \(m\) bits, discard the leftmost bit; otherwise, pad with zeros on the left to ensure the length is \(m\).

Note: For internal processing, each binary string is padded to 30 digits (using leading zeros) to simplify operations. However, the fixed width used for the increment operation is based on the original string's length.

inputFormat

The first line contains two integers n and q — the number of binary strings and the number of queries, respectively.

The next n lines each contain a binary string.

The following q lines each contain a query in the format: type l r, where type is either 1 or 2, and l and r are 1-indexed positions.

outputFormat

For each query of type 1, output the resulting integer on a separate line.

## sample

4 3
0101
1010
1111
0011
1 2 3
2 1 4
1 2 4

10
0

</p>