Flipping Colors

Time limit1sMemory limit128 MB

Summary
Repeatedly split each rectangle in fixed ratios h:v and flip the colors of the upper-right and lower-left parts; report the color reached by each query point.
Level

Medium5 of 10

Topics
Recursion, Divide and conquer, Math, Implementation
Solved
No attempts yet

Problem

A rectangle whose sides are parallel to the xx- and yy-axes, with its lower-left corner at (0,0)(0, 0), is being painted. You may think of the rectangle as a display of almost infinite resolution; initially the whole rectangle is black. Two real numbers 0<h<10 < h < 1 and 0<v<10 < v < 1 are given, and then the following process is applied.

  • Draw a vertical line that splits the horizontal sides of the rectangle in the ratio h:1−hh : 1-h measured from the left.
  • Draw a horizontal line that splits the vertical sides of the rectangle in the ratio v:1−vv : 1-v measured from the bottom.
  • These two lines divide the rectangle into four smaller rectangles.
  • The upper-left and the lower-right sub-rectangles keep their color unchanged.
  • The other two sub-rectangles (upper-right and lower-left) have their color flipped (black to white or white to black), and each of them is then subjected to exactly the same process that was just applied to the bigger rectangle.
  • This process continues (in principle) forever.

Given a point inside the original rectangle that never lies on the boundary of any rectangle appearing during the painting process, determine the color of the point.

Input

The input consists of several test cases. The first line of each case contains four real numbers: the width HH and the height VV of the rectangle, followed by the ratios hh and vv (with 0<h,v<10 < h, v < 1). Thus the rectangle occupies the region [0,H]×[0,V][0, H] \times [0, V]. The next line contains one integer nn, the number of points to consider. Each of the following nn lines contains two numbers, the xx- and yy-coordinates of a point. The input ends with a line whose four values are all 00 (0 0 0 0), which must not be processed.

Output

For each test case, first print a line of the form Case k:, where kk is the case number starting from 11. Then, for each input point, print the color of that point (black or white) on its own line.

Examples1

  1. Example 1

    Input
    81 32 0.333333333333 0.5
    6
    16 30
    16 25
    16 12.0001
    16 11.9999
    16 7.987654321
    16 7.0123456789
    10 10 0.123456789 0.987654321
    2
    0.432 0.9876
    9.432 0.9876
    0 0 0 0
    
    Expected output
    Case 1:
    black
    black
    white
    black
    white
    white
    Case 2:
    white
    black