Problem D: Stream Processing [Middle II]

Problem D: Stream Processing [Middle II]

Time Limit: 1 Sec  Memory Limit: 16 MB
Submit: 1588  Solved: 422
[Submit][Status][Web Board]


VinceBlack is working on stream processing. There is now an infinite stream of data that can be thought of as producing an integer per second. Your task is to collect each number and then output the current \(k\)th largest number (for all the numbers collected) every 100 seconds . If the currently collected number is less than \(k\), the smallest number is output.

The \(k\)th largest number indicates that if sorted in descending order, this number will be ranked in the \(k\)th position.


The input contains three integers \(t\) \((100\le t\le 10^6)\), \(k\) \((1\le k\le 1000)\) and \(s\) \((0\le s\le 10^5)\).

\(t\) is the number of seconds you need to process

Define \(a(n)=n + \text{sum of the digits of }n\), and the number appearing at \(i\)-th (\(i\) starts at 1) second in the data stream is \(a(i+last\_ans)\).

\(last\_ans=s\) in the beginning and will be updated after each answer is calculated.


\(\lfloor t/100 \rfloor\) integers in a line, represents the answers in each 100 seconds.

Sample Input

1926 8 17 

Sample Output

117 319 623 1024 1529 2131 2840 3649 4559 5571 6686 7906 9219 10624 12127 13737 15447 17258 19171 


More information about \(a(n)\): ref