House Numbers

Time limit1sMemory limit128 MB

Summary
Given add and remove sub-orders over ranges of house numbers, find the set of numbers kept and count how many of each digit 0 to 9 appear across them.
Level

Medium4 of 10

Topics
Implementation, Array, Simulation, Math
Solved
No attempts yet

Problem

NarmakSung runs a hardware shop that makes new digit plates for house numbers. If a house number is 195, for example, he has to create one plate for digit 1, one for digit 9, and one for digit 5. But the orders are not always that simple. He may get orders to make digit plates, for example, for all houses on one side of a street.

Since making several plates of the same digit costs much less than making all digits for each house one by one, he wants to know, for a big order he receives, how many of each digit plate he has to make.

Input

The first number in the input, tt (1≤t≤101 \le t \le 10), is the number of orders. Following this, tt orders are given. Each order starts with a line containing a street name, an arbitrary string of length at most 50 characters. The next line contains a single integer NN (1≤N≤101 \le N \le 10), the number of sub-orders, followed by NN lines of sub-orders. Sub-orders are of three kinds:

  • A single house number: the sub-order line contains only a single integer nn (1≤n≤99991 \le n \le 9999).
  • A series of house numbers: the sub-order line starts with a +, followed by three integers a,b,ca, b, c (1≤a,b,c≤99991 \le a, b, c \le 9999). This means plates must be made for house numbers from aa up to bb with step cc; that is, for a,a+c,a+2c,…,ba, a+c, a+2c, \dots, b. It is guaranteed that a<ba < b, that b−ab - a is a multiple of cc, and that c≤b−ac \le b - a.
  • A series of house numbers to be excluded: the sub-order line starts with a -, followed by three integers under exactly the same conditions as above.

If a house number is ordered more than once across separate sub-orders, it is counted only once as long as it is never excluded (like number 100 in the second order). If a house number is excluded anywhere in an order, it cancels every order for that number, even if the number appears later (like number 500 in the second order). It is also possible to exclude numbers that never appear in any other sub-order; such numbers are simply ignored (like 900 in the second order).

Output

For each input order, one set of output data consisting of 13 lines is written. Each set starts with one line containing the street name exactly as it appeared in the input order. The next line must be of the form C addresses, where CC is the total number of house numbers to be made. In the special case C=1C = 1, the line must read 1 address. The next 10 lines must have the following form: line ii contains the number of digit plates needed for digit ii. These 10 lines use the format Make X digit Y, where XX is how many copies of digit YY (YY from 0 to 9) are needed. The last line states the total number ZZ of digits needed, in the format In total Z digits. If only one digit must be produced, it must read In total 1 digit to be grammatically correct. The output is case-sensitive.

Examples2

  1. Example 1

    Input
    2
    Azadi Street
    2
    + 101 103 2
    275
    Sharif Highway
    3
    100
    - 500 900 100
    +  100 800 100
    
    Expected output
    Azadi Street
    3 addresses
    Make 2 digit 0
    Make 3 digit 1
    Make 1 digit 2
    Make 1 digit 3
    Make 0 digit 4
    Make 1 digit 5
    Make 0 digit 6
    Make 1 digit 7
    Make 0 digit 8
    Make 0 digit 9
    In total 9 digits
    Sharif Highway
    4 addresses
    Make 8 digit 0
    Make 1 digit 1
    Make 1 digit 2
    Make 1 digit 3
    Make 1 digit 4
    Make 0 digit 5
    Make 0 digit 6
    Make 0 digit 7
    Make 0 digit 8
    Make 0 digit 9
    In total 12 digits
    
  2. Example 2

    Input
    1
    Main St
    1
    5
    
    Expected output
    Main St
    1 address
    Make 0 digit 0
    Make 0 digit 1
    Make 0 digit 2
    Make 0 digit 3
    Make 0 digit 4
    Make 1 digit 5
    Make 0 digit 6
    Make 0 digit 7
    Make 0 digit 8
    Make 0 digit 9
    In total 1 digit