Chef has a New Kitchen

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese
Chef recently bought a new kitchen. This kitchen is huge! It is rectangular in shape with dimensions W × H, where W is the width and H is the height, both in meters. The kitchen is divided into a grid with W * H individual cells, each of size (1 meter) × (1 meter), and each cell is identified by two integers (x, y) denoting the column and row number of the cell, respectively (1 ≤ x ≤ W and 1 ≤ y ≤ H).
Chef has recently become lazy so instead of walking through his kitchen to work, he just sits forever at his chair located at (x_{C}, y_{C}). However, he sometimes needs to inspect individual locations (for example, to check if his personnel have become lazy too!). Instead of walking towards that location, he just uses a bunch of cheap robots with cameras. These robots are so cheap that Chef has an infinitely many number of them. However, their cheap parts pose a few severe limitations:
 Each robot can only move forward towards the direction it faces, and can only face a direction parallel to one of the walls of the rectangular kitchen.
 Each robot can only turn at 90 degree angles.
 Each robot can only turn at most once.
Note that a robot starts at Chef's location.
There is no problem initially in all of this, because all cells are reachable from Chef's location (x_{C}, y_{C}). However, when the appliances arrive and are installed in the kitchen, some cells cease to be reachable with a robot (because cheap robots cannot pass through appliances!).
Initially, the kitchen is empty, except for his chair. There are N appliances to be installed. Each appliance has dimensions (1 meter) × (1 meter) and occupies exactly one cell. The i^{th} appliance to be installed in chronological order will be installed in (x_{i}, y_{i}). Now, after the addition of each appliance, Chef wants to know how many cells are still reachable with a robot!
Input
The first line of the input contains five integers W, H, x_{C}, y_{C}, N separated by spaces, denoting the dimensions of Chef's new kitchen W × H, the location of Chef's chair (x_{C}, y_{C}), and number of appliances to add.
The next N lines contain information about the appliances. The i^{th} line (after the first line) contains two integers x_{i} and y_{i}, where (x_{i}, y_{i}) is the location of the ith appliance.
Output
Output N lines, where the ith line contains the number of reachable locations after adding the first i appliances.
Constraints
 1 ≤ N ≤ 10^{5}
 1 ≤ W, H ≤ 10^{5}
 1 ≤ x_{C}, x_{i} ≤ W
 1 ≤ y_{C}, y_{i} ≤ H
 No two appliances occupy the same position, and no appliance occupies Chef's position.
Example
Input:20 10 4 3 5 6 5 7 4 8 4 9 3 4 2
Output:199 197 195 159 133
Explanation
The following image illustrates the states of the kitchen after all appliances have been added.
Author:  kevinsogo 
Editorial  http://discuss.codechef.com/problems/CHEFNKCH 
Tags  kevinsogo, range, rangetrees, snck15fl, sqrtdecomp 
Date Added:  17062015 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 