NPC2015B - Eefun the Accountant

no tags 

Eefun is an accountant. As an accountant, he loves to work with spreadsheet. In spreadsheet, a data must be saved into a single cell which has row and column. Spreadsheet has an interesting feature. It can move the cursor from a cell to another cell by clicking a button based on this rules :

  • If current cell has data and its right neighbour also contain data, then clicking the right button will make the cursor move to the first cell to the right of the current cell whose right neighbour doesn't contain data. If there is no such cell, then the cursor will move to the rightmost cell in the current row.
  • Else, then clicking the right button will make the cursor to move to the first cell in the right of current cell which has data. If there is no such cell, then the cursor will move to the rightmost cell in the current row.

Same rules apply when clicking the left, up, and down button.

Eefun realizes this feature which makes him curious. He currently has a lot of data in his spreadsheet. He wants to edit a data on cell (R, C), but first he must move his cursor to the desired cell. Currently his cursor is at cell (1,1), the top-leftmost cell in the spreadsheet. Eefun wants to know the minimal number of button clicked to reach the cell.

Input

First line of input consists of 2 integers, N and M, the number of rows and number of columns
Second line consists of a number X, the number of data that Eefun currently has.
Next X lines each consists of 2 integers, A and B which denotes the position of the data
Line (X+3) contains a number Q, the number of query.
Next Q lines each consists of 2 integers, R and C, the position of cells that Eefun wants to edit 

Output

For each query, output a single integer, the minimum number of buttons that Eefun should click to reach cell (R,C). If the cell cannot be reached, then output a string "Eefun gagal mengedit data"
"Eefun gagal mengedit data" means "Eefun fails to edit his data" 
Note that each query is independent, so Eefun's initial cursor will be at (1,1) for each query

Example

Input:
3 3
8
1 1
1 2
1 3
2 1
2 3
3 1
3 2
3 3
2
3 2
1 3

Output:
Eefun gagal mengedit data
Note : You can try this in Microsoft Excel using ctrl + arrow button

Constraints:

  • 1 ≤ X ≤ min(100.000 , N*M)
  • 1 ≤ N,M ≤ 10.000
  • 1 ≤ Q ≤ 100.000

hide comments
smso: 2023-12-21 09:51:55

According to 2nd rule:
Else, then clicking the right button will make the cursor to move to the first cell in the right of current cell which has data ...

so:
[o]xox... => o[x]ox...
instead of what is given below:
[o]xox... => ox[o]x...
Please clarify.

Ishan: 2022-10-13 08:00:15

Lots of Typos:
By "which it's right neighbour" the author means "whose right neighbour"
By "Next N lines" the author means "Next X lines"
By "Line (N+3) contains" the author means "Line (X+3) contains"

[Simes]: corrected, thanks

Last edit: 2022-10-13 16:34:01
Rishav Goyal: 2016-08-26 09:17:04

actual microsoft excel does not work what you said! self-contradictory statement!

sumbayak_ae: 2016-04-09 02:42:18

what is this edit cells means? did after each edit querys, if the cell contains data it will be deleted, and vise versa, or what?

Matthew Garrison: 2016-02-25 04:13:06

Can the coordinates for the squares with data be outside the range of the grid (ie. not valid coordinates)? Can the coordinates for the queries?

Arianto Wibowo: 2015-12-25 11:20:49

Sorry, there's a slight error in problem description. I've fixed it so hopefully it's not vague anymore

@Min_25:
[o]xx...x => oxx...[x]
[o]xox... => ox[o]x...

and yeah (1,1) => 0 clicks

@Matthew Garrison:
A is row and B is column

Min_25: 2015-12-25 04:27:44

EDIT: *snipped*

(1, 1) => (1, 1): 0 clicks.

@Arianto Wibowo
Thank you for the clarification.

Last edit: 2015-12-25 14:08:56
Matthew Garrison: 2015-12-18 16:05:24

For the position of the data, A and B, which is the row # and which is the column #?

Is it (A, B) or (B, A), where (x, y)?

Alex Anderson: 2015-11-11 08:00:17

Interesting problem, I wonder why others have not tried to solve.

Seems problem statement is a little vague, but you can make reasonable assumptions.
Q: Is each query independent? Or after moving to R1,C1, he tries to move from there directly to R2,C2? (I assume they are independent).
Q: If the queries aren't independent, after a query to R1,C1, is there now data in R1,C1? (I assume independent, so, no changes between queries).

Last edit: 2015-11-11 08:49:04

Added by:Louis Arianto
Date:2015-10-10
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:NPC Schematics 2015