Floating Mountain Stability

Time limit1sMemory limit128 MB

Summary

Given up to 49 surviving terms, decide whether they can be a subsequence of a generalized Fibonacci sequence with at most 8 skipped terms between consecutive survivors, and output a valid witness.

Level: Hard8 of 10
Topics: Math, Number theory, Brute force, Implementation
Solved: No attempts yet

Problem

Floating mountains are stacked into towering structures. Scientists conjecture that, when a structure first formed, the sizes of its stacked mountains followed a generalized Fibonacci sequence: an integer sequence in which every term equals the sum of the two preceding terms,

$t_i = t_{i-1} + t_{i-2}.$

Such a sequence is completely determined by any two consecutive terms and extends infinitely in both directions. Because the mountains contain unusual materials, some sizes may be negative.

Over time, mountains are destroyed or drift away, so a real structure preserves only a subsequence of the original sizes. The scientists believe that only a few mountains are ever missing between two survivors. Concretely, in a stable structure every pair of consecutive surviving sizes is at most 9 positions apart in the original generalized Fibonacci sequence — that is, at most 8 sizes lie strictly between them.

Given the surviving sizes in order, decide whether they can be a subsequence of some generalized Fibonacci sequence under this gap limit.

For instance, the sizes 0 6 16 are stable, because they appear in the generalized Fibonacci sequence

0 2 2 4 6 10 16

where 0 and 6 are only 4 positions apart.

As another instance, -22 8 77 125 is also stable, drawn from

37 -22 15 -7 8 1 9 10 19 29 48 77 125

Input

The first line contains the number of test cases $n$ . Each of the next $n$ lines describes one structure: an integer $k$ ( $1 \le k < 50$ ), the number of surviving sizes, followed by the $k$ sizes in order. Every size $v$ satisfies $-2^{30} < v < 2^{30}$ .

Output

For each test case, print one line. If the surviving sizes are stable, print STABLE followed by the first five terms of a valid original generalized Fibonacci sequence, starting at the first surviving size. Otherwise print UNSTABLE. When several original sequences are possible, choose the one whose first two surviving sizes have the smallest gap (the fewest missing terms between them); this choice makes the first five terms unique.

Examples3

Example 1

Input

3
3 0 6 16
4 -22 8 77 125
4 1 1 1 1

Expected output

STABLE 0 2 2 4 6
STABLE -22 15 -7 8 1
UNSTABLE

Example 2
Input
```
1
2 5 8
```
Expected output
```
STABLE 5 8 13 21 34
```
Example 3
Input
```
1
5 1 2 5 13 34
```
Expected output
```
STABLE 1 2 3 5 8
```