ASCDFIB  Ascending Fibonacci Numbers
John is trying to learn the Fibonacci sequence. This is what he has learned so far. The first two terms of the sequence are f(1) = 0 and f(2) = 1. The next term f(n) is then calculated by adding the previous two terms f(n1) and f(n2). Therefore,
f(1) = 0
f(2) = 1
f(3) = f(2) + f(1) = 1 + 0 = 1
f(4) = f(3) + f(2) = 1 + 1 = 2
f(5) = f(4) + f(3) = 2 + 1 = 3
f(6) = f(5) + f(4) = 3 + 2 = 5
After calculating this for a while, John realized that the values are becoming too big. In order to keep the values small, John changed his algorithm. Instead of calculating f(n) = f(n1)+f(n2), he decided he will calculate f(n) = ( f(n1)+f(n2) ) % 10^5.
Now John wants to do some research on his new modified Fibonacci sequence. He will give you an integer A (A<=10^5) and an integer B (B<=10^6). You have to output all the terms from f(A) to f(A+B) in ascending order (nondecreasing order). But printing so many numbers is too much of a hassle. So, if there are more than 100 terms in the output, then only print the first 100.
Input
The first line contains an integer T (T<=100), which is the number of test cases.
Each test case contains two positive integers A and B as mentioned before.
Output
For each test case, print case number (Check sample output) and then print the terms from f(A) to f(A+B) in ascending order (nondecreasing order). If there are more than 100 terms in the output, then only print the first 100.
Example
Input:3 1 3 3 3 100 1 Output:
Case 1: 0 1 1 2 Case 2: 1 2 3 5 Case 3: 15075 69026
hide comments
vidusheeamoli:
20180531 18:34:55
Counting sort :) 

karthik_vg:
20180310 17:08:59
matrix expo did the thing nice one (y) 

code_aim:
20171020 20:19:27
One of the worst problem statement. It should be made more clearer. 

pruthi_vishal:
20170129 10:25:27
Finally AC after 2WAs ...... Read the problem carefully before proceeding.......!!!!!!! 

coder_hsnake:
20170122 21:09:00
After 6 REs,1CE,1WA,3TLEs finally AC plz take array size for fibonacci 1100000 and use hashing not sorting :)


nightwolf_9197:
20160523 00:12:08
@forthright48: why is my code getting RE : SIGXFSZ error 

darkhire21:
20160102 19:51:20
after 1 month moved from todo to AC...!!! 

eightnoteight:
20150905 08:08:13
enjoyed solving it in python 

Glenda Emanuella Sutanto:
20150619 06:25:06
finally AC after 2 WAs and 1 TLE!!! :))) i just changed it into counting sort and it got AC xD 

Glenda Emanuella Sutanto:
20150618 06:35:17
@samiul / the problem setter : my submission 14478814 please check it, thankyou so much 
Added by:  forthright48 
Date:  20130913 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Editorial 