Little L, as an OIER, has solved the well-known grid counting problem.

Given an infinitely large grid, the position at row $i$ and column $j$ is denoted as $(i,j)$. Several positions on the grid are marked. It is guaranteed that $(1,1)$ is marked. A piece starts at $(1,1)$, and in each step, it can only move right or down (i.e., increment one of the coordinates by 1). The piece can only pass through marked positions. For all positions, calculate the number of ways to reach that position.

However, Little L thinks this is too simple. Let $f_{i,j}$ be the number of ways to reach position $(i,j)$ (if the position cannot be reached, $f_{i,j}=0$). He wants to select a set of distinct positions such that the sum of their $f$ values equals a given number $k$. If there are multiple solutions, you may output any one of them. Little L will make $Q$ such queries.

Little L wants to minimize the number of selected positions for each query, and at the same time, he wants to minimize the number of marked positions on the grid. Please construct a solution that satisfies these conditions.

Specifically, Little L requires that the number of marked positions on the grid does not exceed $X$, and the number of positions selected for each query does not exceed $Y$.

Input

The first line contains four positive integers $K, Q, X, Y$. It is guaranteed that all queried $k$ satisfy $1 \le k < 10^K$.

The next $Q$ lines each contain an integer $k$.

Output

The first line contains a positive integer $n$, representing the number of marked positions on the grid. You must ensure $n \le X$.

The next $n$ lines each contain two integers $x, y$, representing the coordinates of a marked position. You must ensure that the marked coordinates are distinct. Note the output order (which will be relevant later). Although the grid is infinite, you must ensure that the output coordinates $x, y$ satisfy $1 \le x, y \le n$.

The next $Q$ lines each contain a binary string of length $n$, where the $i$-th character being '1' means you have selected the $i$-th marked coordinate.

You must ensure $n \le X$, and the number of '1's in each binary string does not exceed $Y$.

Examples

Input 1

2 3 1000 340
1
2
3

Output 1

8
1 1
1 2
1 3
2 1
2 3
3 1
3 2
3 3
10000000
00000110
10000001

Note

The grid is as follows:

The top-left corner is cell $(1,1)$ and the bottom-right is $(3,3)$. Yellow cells are unmarked. The numbers in the cells are the corresponding $f$ values. Of course, the grid size is larger than $3 \times 3$; only the region containing marked cells is shown here.

For the first query, cell $(1,1)$ was selected. For the second query, cells $(3,1)$ and $(3,2)$ were selected. For the third query, cells $(1,1)$ and $(3,3)$ were selected.

A checker.cpp is provided in the download files. You can compile it into an executable. Its usage format is checker chess.in chess.out, where chess.in is the input file and chess.out is your output. The checker will perform validation and return an error code:

1. Output format error (including $n > X$, but excluding the case where the number of '1's in the binary string is $> Y$).
2. The number of '1's in the binary string is $> Y$.
3. The sum of $f$ values of your constructed solution is not equal to the required value for the query.

If your construction is correct, the checker will return correct.

You may refer to or directly use the high-precision template provided in the checker.

Note that the provided checker may differ from the actual one used for judging.

Constraints

In the random data, $k$ is chosen uniformly at random from $[1, 10^K)$.

For all test cases, it is guaranteed that $1 \le Q \le 10^4$.