Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

HS12RTP - Rectangles Packing

You might be aware of the Packing Problem or the Perfect Square Dissection problem known from the Scottish Book. Here, your task is similar: given a rectangle R and a given set S of rectangles: r1, r2, ... rn try to pack axis-aligned rectangles from S into R in such a way that the unused space in R is as small as possible.

Input

First, you are given t (t < 100) - the number of test cases. Each of the test cases starts with two integers: Rx, Ry - describing the size of R. In the next line you are given n (n < 100) - the number of objects in the set. In the successive n lines, the descriptions of the S elements follow. The i-th line consists of two integers: rxi, ryi - the size of ri.

Output

For each of the test cases output k (0 <= k <=n ) - the number of elements from S you pack into R and in the successive k lines: i - the number of the rectangle to use, xi, yi - the coordinates of ri in R and one character: either o (for original alignment) or r (for rotated alignment).

Coordinates are relative to R. Coordinates of vertices of R are: (0,0), (Rx, 0), (Rx, Ry), (0, Ry). Coordinates of vertices of a rectangle ri: i xi yi o are: (rxi, ryi), (rxi+xi, ryi), (rxi+xi, ryi+yi), (rxi, ryi+yi), while coordinates of vertices of a rotated rectangle ri: i xi yi r are: (rxi, ryi), (rxi+yi, ryi), (rxi+yi, ryi+xi), (rxi, ryi+xi).

Do not use the same ri twice. No two different ri, rj may overlap.

Scoring

The score awarded to your program for a given test case is the area of the used rectangles.
The score awarded to your program for a given test set is the sum of points awarded for all cases in the set.
The overall score of the program is the sum of scores obtained for correctly solved test sets.

The number of points given in the ranking is scaled so that it is equal to 10 for the registered contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.

Example

Input:
3

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

6 2
3
1 5
1 5
1 2

3 3
1 
4 4
 
Output:
4
5 1 1 o
1 0 0 r
2 3 0 o
3 0 1 o

3
1 0 0 r
2 0 1 r
3 5 0 o

0

Scoring: The exemplary solution will score 57 points (45 + 12 + 0).

Input data sizes

 s    t     n     Rx*Ry  l 
 1    10   <20    <40    2s
 2    10   <20    <100   2s
 3    10   <30    <120   2s
 4    10   <30    <400   2s
 5    10   <50    <200   2s
 6    20   <40    <10    5s
 7    20   <100   <10    5s
 8    20   <40    <2500  5s
 9    20   <80    <2500  5s
10    20   <100   <10000 5s

 s   - test set number 
 t   - the number of test cases
 n   - the number of rectangles
 x*y - the size of R
 l   - time limit

Please note

  • Till the last week of the series, all submitted codes will be visible to all users and tested on temporary data sets only.
  • For the last week of the series, submissions will be visible to the submitting contestant, only, and tested on the full set of test cases. (All earlier solutions will be rejudged).

Added by:kuszi
Date:2012-12-12
Time limit:2s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 CLOJURE PERL6
Resource:High School Programming League 2012/13

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.