Analyzing Collatz-like sequences We define a Collatz-like sequence s with 4 positive integers:


n starting value
d &gt; 1 divisor
m &gt; 1 multiplier
i increment


(In the original Collatz sequence d = 2 m = 3 and i = 1.)

Given these integers s will be created in the following manner:


s(0) = n
if k &gt; 0 and s(k-1) mod d = 0 then s(k) = s(k-1) / d
if k &gt; 0 and s(k-1) mod d != 0 then s(k) = s(k-1) * m + i


An example sequence with d = 2, m = 3, i = 5 and n = 80 will be s = 80, 40, 20, 10, 5, 20, 10, 5, 20, ....

Every sequence will either reach higher values than any given bound (i.e. the sequence is divergent) or get into an infinite loop if for some t and u (t!=u) the s(t) = s(u) equality will be true.

In our problem if the value of a sequence element is larger than 10^9 or there is no element repetition before the 1000th element the sequence is considered divergent.

The task

You should write a program or function which takes the positive integers d m and i as inputs and outputs all the different ending types of the sequences (infinite loops and divergence) which the starting values n = 1, 2, 3, ... 999, 1000 can produce.

Input details


The input is a string or list (or closest equivalent in your language) representing (in the common way) three positive integers d, m and i in that order. d and m are at least 2. Neither number is larger than 100. 


Output details

The output specification is a bit wordy. Might worth to check out the examples first.


You should output to the standard output (or closest alternative) or return a string.
If divergent sequence is possible the first line should be DIVERGENT.
A unique representation of a sequence's loop is it's rotation where the smallest number is the last separated by spaces. E.g. if s = 2 1 4 2 1 4 2 1 the loop is 4 2 1.
In every following line you should output every unique loop exactly once preceded by the word LOOP. E.g. LOOP 4 2 1
The loops should be in ascending order in regard of their last element.
Trailing newline is optional.


Examples:

The first lines are the inputs and the following ones until a blank line are the outputs.

2 3 1
LOOP 4 2 1

2 2 6
LOOP 8 4 2 1
LOOP 12 6 3

3 7 8
DIVERGENT
LOOP 15 5 43 309 103 729 243 81 27 9 3 1
LOOP 22 162 54 18 6 2
LOOP 36 12 4

3 9 1
DIVERGENT

6 9 9
DIVERGENT
LOOP 18 3 36 6 1
LOOP 27 252 42 7 72 12 2
LOOP 45 414 69 630 105 954 159 1440 240 40 369 3330 555 5004 834 139 1260 210 35 324 54 9 90 15 144 24 4
LOOP 81 738 123 1116 186 31 288 48 8
LOOP 99 900 150 25 234 39 360 60 10
LOOP 126 21 198 33 306 51 468 78 13

10 10 10
LOOP 20 2 30 3 40 4 50 5 60 6 70 7 80 8 90 9 100 10 1

93 91 92
DIVERGENT
LOOP 2185 198927 2139 23
LOOP 4278 46


Reference implementation in Python 3 on Ideone.

This is code-golf so shortest entry wins.
Python 3, 269 254 252 246 bytes

d,m,i=eval(input())
S=set()
for n in range(1,1001):
 T=X=()
 while len(T)**3&lt;1e9&gt;=n:
  T=(n,)+T;n=[n//d,n*m+i][n%d&gt;0]
  if n in T:I=T.index;L=T[:I(n)+1];M=I(min(L));X=L[M:]+L[:M]
 S|={X}
for x in sorted(S):print(x and&quot;LOOP&quot;or&quot;DIVERGENT&quot;,*x[::-1])

(Now 10 times slower to save a few bytes. Typical code golf.)
Input a list via STDIN (e.g. [2, 3, 1]). I'm thinking that there's got to be a better way of standardising the cycles...
The approach is quite straightforward — test all 1000 numbers and take only the unique outputs. However, there are two little tricks in there:

Loops are represented by nonempty tuples, but more importantly divergence is represented by an empty tuple. This is good because:

It doesn't break sorted, and will even appear before all the loop tuples
It allows us to select a string via x and&quot;LOOP&quot;or&quot;DIVERGENT&quot;
*()[::-1] doesn't affect print


The loops are built backwards to turn &quot;sort ascending by last element&quot; into &quot;sort ascending by first element&quot;, which removes the need to pass a lambda into sorted.


Previous submission, 252 bytes
d,m,i=eval(input())
def f(n,T=()):
 x=[n//d,n*m+i][n%d&gt;0];I=T.index
 if x in T:L=T[:I(x)+1];M=I(min(L));return L[M:]+L[:M]
 return()if(T[1000:]or x&gt;1e9)else f(x,(x,)+T)
for x in sorted(set(map(f,range(1,1001)))):print(x and&quot;LOOP&quot;or&quot;DIVERGENT&quot;,*x[::-1])

This one's a lot faster.