Problem Description

Consider a tower made of blocks that are $1 \times w \times (w \times n)$ rectangular prisms. Each level consists of $n$ blocks, with every two levels placed at right angles to each other, forming a total of $h$ levels. There are $m$ operations to remove blocks, where for the $i$-th operation, the block to be removed is specified by its level $l_i$ (counted from the bottom) and its position $k_i$ (counted from the back-left to the front-right). If all blocks on one side or in the middle (if $n$ is even, the middle is ignored) of a level are removed, the tower collapses.

Input Format

The first line contains two integers $n$ and $w$ ($1 \le n, w \le 10000$). The second line contains two integers $h$ and $m$ ($1 \le h, m \le 5000$). The following $m$ lines contain the integers $l_i$ and $k_i$ ($1 \le l_i \le h; 1 \le k_i \le n$). Each block can only be moved once.

Output Format

If the tower collapses, output "yes". Otherwise, output "no". In the former case, output the number of the operation just before the collapse on the next line.

Problem Description

Jane is a game designer who is creating the next version of Jenga Boom, where the blocks have dimensions of $1 \times w \times w_n$ instead of the standard $1 \times 2 \times 6$. The initial tower is constructed with $n$ blocks per level, placed next to each other along their long sides and at a right angle to the previous level. Players take turns removing blocks until the tower collapses.

Jane wants to build a game simulator to help her determine the optimal $n$ and $w$. The simulator should calculate the moment when the tower collapses if blocks are removed in a specified order. The tower collapses if there is a cross-section such that the center of mass of the levels above it does not lie within or at the edge of the convex hull of the projection of the previous level.

Input Format

The first line contains two integers $n$ and $w$ that define the block dimensions as described in the problem statement ($1 \le n, w \le 10000$). The second line contains two integers: $h$ -- the number of levels in the tower and $m$ -- the number of removed blocks ($1 \le h, m \le 5000$).

The next $m$ lines contain the coordinates of the removed blocks with two integers each: $l_i$ -- the level of the block, counting from the bottom, and $k_i$ -- the position of the block, counting from the edge nearest to the players ($1 \le l_i \le h; 1 \le k_i \le n$). Blocks are removed one by one, and no block is removed twice.

Output Format

In the first line, output yes if the tower collapses, and no otherwise. In the former case, output the number of the block (starting from 1) that was removed just before the collapse on the next line.

Sample Input and Output

Input Sample #1

5 2
6 6
4 1
4 2
4 5
5 3
4 3
1 1

Output Sample #1

yes
5

Input Sample #2

3 3
10 1
10 3

Output Sample #2

no

Input Sample #3

2 2
2 1
1 1

Output Sample #3

yes
1

Notes/Hints

Time limit: 2 seconds, Memory limit: 512 MB.

见题面 Input 部分

见题面 Output 部分