Serena is learning about binary numbers in math class! She is given a binary number , and she is also given series of operations which she must perform on it. In one operation, she sets all bits in the 1-indexed range to , and outputs the base-10 value of the binary number, modulo .
The base-10 value of a binary number of length consisting of digits and is given by the sum of over all in .
The first line contains two space-separated integers, and , the length of the number and the number of operations.
The next line contains , the original binary number.
The next lines contain two space-separated integers, and , representing an operation described in the problem statement.
For each operation, output the base-10 value of the binary number after performing the operation, modulo .
In all subtasks,
Subtask 1 [20%]
Subtask 2 [80%]
No additional constraints.
Sample Input 1
5 2 01000 1 3 2 4
Sample Output 1