Elliot's Messy Notes

Description

Your friend Elliot is terrible at math and wants to cheat on his upcoming series test. Luckily, he was able to snag a look at the test paper by sneaking into the math office, but unfortunately, he was unable to find the answer sheet and forgot some terms. It's up to you, his dearly programmer friend, to find the $N$-th term of each series he provides.

Elliot tried to copy the sequences from the test paper, but his notes are a complete disaster:

• About 25% of the terms are missing (written as _).
• Of the numbers that are present, about 25% are wrong (simple typos or errors).
• Only the remaining 50% are correct.

Your job is to extract the underlying series from this noisy data, decide whether it follows one of the three allowed patterns, and output the $N$-th term.

The allowed patterns are:

1. Arithmetic: $T_n = T_{n-1} + D$ (adds a constant difference).
2. Geometric: $T_n = T_{n-1} \times R$ (multiplies by a constant ratio).
3. Recursive (Fibonacci-style): $T_n = T_{n-1} + T_{n-2}$ (adds the previous two terms).

Pattern Validity

Let $K$ be the number of known (non-_) entries. A pattern is considered valid if it matches strictly more than half ($> 50\%$) of those $K$ entries (i.e., matches $> K/2$ known terms).

Multiple Valid Patterns

If two (or all three) patterns each satisfy the "> 50%" rule, they all count. Print their $N$-th terms on one line, separated by the literal string OR (order does not matter).

No Valid Patterns

If none of the three patterns meets the rule, print INVALID.

Numeric Domain

• Input terms may be integers or decimals (e.g., -3, 2.75).
• Internally, you must use exact rational arithmetic—no rounding errors are allowed in your checks or calculations.
• The final answer(s) must be printed:
  • With the least number of decimal places that still shows the value accurately.
  • Rounded (not truncated) to at most 6 fractional digits.
  • Never in scientific notation.
  • Examples: 6.5, 3, 0.333333.

The answer(s) are guaranteed to fit in a signed 64-bit integer if written as an exact rational (though they may be decimals when printed).

Input Specification

The input consists of two lines:

1. The first line contains two integers $M$ and $N$, separated by a space.
   • $M$ is the length of Elliot's list ($5 \le M \le 20$).
   • $N$ is the 1-based index of the term to find ($1 \le N \le 10,000,000$).
2. The second line contains $M$ space-separated items: either a number (integer or decimal) or the underscore _ for missing terms.

Constraints:

• Known terms are between $-10^9$ and $10^9$ in absolute value.
• _ may appear anywhere.

Output Specification

Output a single line containing:

• A single value if exactly one pattern is valid.
• Multiple values separated by OR (e.g., value1 OR value2) if several patterns are valid.
• INVALID if no pattern is valid.

Sample Cases

Sample Input

Sample Output