Problem Description

In a certain temple, a New Year's ritual is held every year.

The ritual uses $ R $ × $ C $ stone statues. The statues are arranged in $ R $ rows (north-south direction) and $ C $ columns (east-west direction). The statue at the northwest corner is the starting point, and the statue that is $i-1\ (1\ ≦\ i\ ≦\ R)$ steps south and $j-1\ (1\ ≦\ j\ ≦\ C)$ steps east from it is called statue ($ i $,$ j $). Initially, all statues face south.

The ritual consists of $ N $ steps, and the $s\ (1\ ≦\ s\ ≦\ N)$th step is as follows:

• Step $ s $: For all integer pairs ($ u $,$ v $) satisfying $r_{a,s}\ ≦\ u\ ≦\ r_{b,s}$ and $c_{a,s}\ ≦\ v\ ≦\ c_{b,s}$, rotate statue ($ u $,$ v $) 90 degrees to the left.

Usually, these steps are performed $ N $ times, but this year, one step was forgotten, resulting in a different final outcome than usual.

Each step has important meaning, so leaving it out would cause significant issues.

To make matters worse, the directions of the statues after $N\ -\ 1$ steps were not recorded. However, it was fortunately noted that $ M $ statues were facing south at the end.

A meeting was held in the temple to create a program that lists the forgotten steps, but there are no programmers in the temple. Your task is to create a program that lists the forgotten steps in the ritual.

Input Format

The input is given from the standard input in the following format:

$ R $ $ C $ $ M $ $ N $ $ r_{a,1} $ $ r_{b,1} $ $ c_{a,1} $ $ c_{b,1} $ $ r_{a,2} $ $ r_{b,2} $ $ c_{a,2} $ $ c_{b,2} $ : $ r_{a,N} $ $ r_{b,N} $ $ c_{a,N} $ $ c_{b,N} $

• The first line contains the number of rows $R\ (1\ ≦\ R\ ≦\ 50)$, columns $C\ (1\ ≦\ C\ ≦\ 50)$, and the number of statues facing south at the end $M\ (0\ ≦\ M\ ≦\ R\ ×\ C)$, separated by spaces.
• The second line contains the number of steps $N\ (1\ ≦\ N\ ≦\ 5,000)$.
• The next $ N $ lines contain information about each step. The $i\ (1\ ≦\ i\ ≦\ N)$th line contains four integers $ r_{a,i} $, $r_{b,i}\ (1\ ≦\ r_{a,i}\ ≦\ r_{b,i}\ ≦\ R)$, $ c_{a,i} $, $c_{b,i}\ (1\ ≦\ c_{a,i}\ ≦\ c_{b,i}\ ≦\ C)$, separated by spaces. This indicates that step $ i $ rotates the statues ($ u $,$ v $) 90 degrees to the left for all integer pairs ($ u $,$ v $) satisfying $r_{a,i}\ ≦\ u\ ≦\ r_{b,i}$ and $c_{a,i}\ ≦\ v\ ≦\ c_{b,i}$.
• For any input, at least one step may have been forgotten (i.e., there is at least one solution).

Output Format

When the forgotten steps in the ritual are step $ f_1 $, step $ f_2 $, ..., step $ f_m $ in ascending order, output $ m $ lines. The $l\ (1\ ≦\ l\ ≦\ m)$th line should contain the integer $ f_l $. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2
6

Sample Input #2

4 4 8
9
1 4 1 4
1 4 1 4
1 4 1 1
1 4 3 3
1 2 1 2
1 2 3 4
3 4 1 2
3 4 3 4
1 4 1 4

Sample Output #2

1
2
5
6
7
8
9

Notes/Hints

Sample Explanation 1

In the initial state, all statues face south. For example, if step $ 2 $ is forgotten, the behavior is as follows:

After step $ 1 $, each statue faces:
south east east east east
south east east east east
south east east east east

After step $ 3 $, each statue faces:
east north north north east
east north north north east
east north north north east

After step $ 4 $, each statue faces:
east north north north east
east west west west north
east west west west north

After step $ 5 $, each statue faces:
east north west west north
east west south south west
east west west west north

After step $ 6 $, each statue faces:
east north west south west
east west south east south
east west west west north

As a result, there are $ 3 $ statues facing south, so step $ 2 $ could have been forgotten. In this example, step $ 6 $ could also have been forgotten, as other cases result in a contradiction. Therefore, output $ 2 $ on the first line and $ 6 $ on the second line.

见题面 Input 部分

见题面 Output 部分