<PREV Problem:
NEXT>
Solved by 139 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Counting figures

Time limit = 8 second(s)

We have paper divided into M x N square cells, black and white. Black cells form joined figure (two cells are adjacent if their intersection is segment).

The description of the black figure is given as union of 1 x L (y-strip) and L x 1 (x-strip) tiles.

Strips can intersect and overlap, but two strips can not start at one cell. Starting cell of a strip is the cell with minimum rating. Cell rating is defined as x*N+y. Coordinates x and y are integers from sets 1..M and 1..N.

Write a program that answers

Question 1. What is the number of white cells?

Question 2. What is the number of joined white figures?

Each strip can be described by four numbers:

1) direction, D, that is 0 or 1: 0 — x-strip, 1 — y-strip;

2-3) coordinates of the starting cell, (X, Y);

4) strip length, L.

Strips are given in the order of starting cells.

Number of strips is less than 256000.

Input

The first line contains number P equal to 1 or 2. The second line contains M and N, 1 ≤ M ≤ 4000, 1 ≤ N ≤ 4000. Then number K follows, 0 ≤ K ≤ 256000, equal to number of strips. Then K lines, each with 4 numbers D X Y L, follow.

Output If P == 1 then output answer to the question 1.

If P == 2 then answer to the question 2.

Input#1
1
40 400
2
1 1 100 40
0 1 101 1
Output#1
15959

Input#2
2
40 400
2
1 1 100 40
1 1 101 1
Output#2
2
 
Input#3
1
6 12
17
0 1 1 10
1 1 4 4
0 1 5 2
0 1 7 6
1 2 1 5
1 2 5 4
0 2 6 1
1 2 12 5
0 3 4 4
0 3 10 3
0 4 2 2
1 4 11 3
1 5 2 1
0 5 6 2
1 5 9 2
0 6 1 2
0 6 5 7
Output#3
22

Input#4
2
6 12
12
0 1 1 12
1 1 12 6
1 2 1 5
0 2 4 3
0 3 4 4
0 3 10 3
1 3 11 4
0 4 1 5
1 5 2 2
0 5 5 3
1 5 9 2
0 6 5 8
Output#4
3

Author:
Moscow school contest, 2004
15 March 2004

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 180ms

SW soft NIX
ID = 54.80.60.91