Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Contact
Time Limit: 5000MSMemory Limit: 32768K
Total Submissions: 2925Accepted: 813

Description

Dr. Astro Insky works at a radiotelescope centre. Recently, she noticed a very curious microwave pulsing emission sent right from the centre of the galaxy. Is the emission transmitted by some extraterrestrial form of intelligent life? Or is it nothing but the usual heartbeat of the stars?

You must help Dr. Insky to find out the truth by providing a tool to analyse bit patterns in the files she records. Dr. Insky wants to find the patterns of length between (and including) A and B that repeat themselves most often in the data file of each day. In each case, the greatest N distinct frequencies (that is, number of occurrences) are sought. Pattern occurrences may overlap, and only patterns that occur at least once are taken into account.

Input

Your program is to read from standard input.
First line - The integer A indicating the minimum pattern length.
Second line - The integer B indicating the maximum pattern length.
Third line - The integer N indicating the number of distinct frequencies.
Fourth line - A sequence of 0 and 1 characters, terminated by a 2 character.

The input may have up to 2 megabytes. The parameters A, B and N are constrained by:
0 < N <= 20
0 < A <= B <= 12

Output

Your program is to write to standard output. The output contains at most N lines, listing the at most N greatest frequencies and corresponding patterns. The listing must be produced in decreasing order of pattern frequency, and consists of lines formatted like

frequency pattern pattern ... pattern

where frequency is the number of occurrences of the patterns that follow. The patterns in each line must appear in decreasing order of length. Patterns of equal length must be listed in reverse numerical order. In case there are less than N distinct frequencies, the output listing will have less than N lines.

Sample Input

2
4
10
010100100100010001111011000010100110011110000100100111100100000002

Sample Output

23 00
15 10 01
12 100
11 001 000 11
10 010
8 0100
7 1001 0010
6 0000 111
5 1000 110 011
4 1100 0011 0001

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator