Please write a program to simulate a game called Battleship. First you need to place ships on an N by N board (1 <= N <= 1000). Every ship will occupy a 1 by k area, where k is an integer between 1 and N. The ships cannot overlap and they can only be placed vertically or horizontally. After placing the ship you can hit them with bombs. Each bomb is specified by an (x, y) coordinate, where both x, and y are between 0 and N - 1. You must report whether each bomb hits or misses the ships.

Question

The first line of the input is the board size N. The next line is the number of ships m, where m is between 1 and 100. The next m line indicates the position of the ships. The first two numbers indicate the position of the first cell of the ship, where (N - 1, 0) is at the right lower corner. The third number is the orientation of the ship, where 1 indicates east bound, 2 for south bound, 3 for west bound, and 4 for north bound. Then the fourth number is the size of the ship k. For example, a line 3 4 4 3 indicates that a ship occupies cell (3, 4), (3, 5), and (3, 6). Note that the ship cannot overlap, so if a ship overlaps with previous ship, it will be ignored. Also all ship must not extend to outside of the board, have incorrect size, incorrect orientation, etc. Any ship that cannot be placed will be ignored. Finally the next line is the number of bombs b. In the next b lines we have the coordinates of the places we will bomb.

The output has b lines, and each line is for a bomb. If the bomb hit a ship. you must print the id of the ship. The id of the ship is from 1 to m, where the fist ship in the input has id 1, etc. If the the bomb does not hit a ship, you must print a 0.

Input Format

There is an positive integer N in the first line, m in the second line, the number of ships.
Following m lines are the descriptions of ship 1..m. Following are a number b and b bomb positions.(See sample input)

Output Format

For every bomb, please output the id of the hit ship. If the the bomb does not hit a ship, you must print a 0.

Sample Input

5
4
1 2 1 3
260 676 8 82
1 1 1 3
0 2 4 3
5
1 1
0 3
0 2
2 2
2 2

Sample Output

3
4
0
1
0

Note:

1. The positions of bombs are always valid.
2. When any position of a ship is invalid, the id is skipped.
3. If a ship is hit, the ship is destroyed and will not be hit again.

Answer 1

You can write this program using almost any current language, VB2008, C++, C, Java, or even Fortran.
I suggest you start with a modest grid like 10x10 to make sure the logic works. But also test first to see if the memory will allow a 1000x1000 grid, which is not big, but considerable.
The program logic is straigth-forward enough. Each program requirement translates to some explicit code, no hidden details. Also, the data structure could simply be a 2-d array, again no complications.

You would do well doing a little design and jump onto coding your problem. Although the logic is relatively simple, it does require quite a bit of detail, for example, it take a few lines of code or a few loops to check for overlaps of the ships. So get your hands (or even knees) wet and get going. You'll be happy you did.