Report 2#2494
Participants of the International Summer School on Programming in Sevastopol (2011) have learned about an institution where documents are numbered in an unusual way. One set of digits is used for odd positions, and generally, another set is used for even positions (positions are counted from right to left, starting from zero). In this institution, two rules are strictly followed:
Numbers within the given constraints are not skipped.
Numbers are arranged in ascending order in the usual sense.
For example, if digits 0, 5, 6 are used for even positions and digits 0 and 7 are used for odd positions, the first few numbers will be: 0, 5, 6, 70, 75, 76, 500, 505, 506, 570, 575, 576, 600, ...
It is believed that several other organizations have decided to adopt this style of document numbering.
The Regional Corporate Development Service has decided to prepare for these developments. They have reasonably concluded that such an organization would extend these document numbering rules to the numbering of pages in its publications, particularly for report pages.
The service asks you to write a program which, given the sets of digits for even and odd positions and the number of report pages, determines for each digit how many times it is used in numbering all the pages of the report.
The first line contains three numbers: , , and . is the number of pages in the report; and are the number of digits used for even and odd positions, respectively. The second line contains the digits used for even positions, separated by spaces; the third line contains the digits used for odd positions. 1 \leq N \leq 10^{10}, 2 \leq L, K \leq 10.
Print a single line containing exactly ten numbers, separated by spaces. The first number is the number of zeros, the second is the number of ones, and so on; the last number is the number of nines. It is guaranteed that the numbers in the output do not exceed 10^{18}.
Example 1