You have a piece of land, which is divided into an n ∗ m grid. In some squares there is a water source capable of providing water for a certain number of other squares. A water source can provide water for zero or more consecutive squares directly to the north, zero or more consecutive squares directly to the east and so on. Water is precious, so you have just enough water to irrigate the whole piece of land. So it’s crucial to design an irrigation system so that every square is either a water source or irrigated by exactly one water source. On the right is an example. Water sources are represented in the form id(water). So the 4-th water is capable of provide water for 5 other squares. Input Fig 1. An irrigation system The input consists of at most 50 test cases. Each case begins with a line containing three non-negative integers n, m and k (1 ≤ n,m ≤ 30,1 ≤ k ≤ 200), where k is the number of water sources. In the following k lines water sources are described, by three non-negative integers x, y, c (1 ≤ x ≤ n, 1 ≤ y ≤ m), the coordinate and water capacity (west-south corner is (1,1)), one line for each water source. It is guaranteed that nm − k = c1 + c2 + . . . + ck (just enough water). The last case is followed by a single zero, which should not be processed. Output For each test case, print the case number in the first line, then k lines followed, one for each water source. Each water source is described by four non-negative integers n, e, s, w, the amount of squares irrigated in each direction. It is guaranteed that at least one solution exists. Print a blank line after each test case. Sample Input 222 111 221 556 132 214 254 335 522 542 0 Sample Output Case 1: 1000
2/2 0010 Case 2: 1010 1201 0211 1211 0011 1001