H. Fibocchi Sequence
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bocchi has recently learned about the Fibonacci sequence (or as she likes to call it, Fibocchi sequence), and has now proclaimed herself the master of the Fibocchi sequence!

Ryou has decided to test this by giving Bocchi the $$$2$$$ starting numbers, $$$a$$$ and $$$b$$$, of the sequence $$$f_k$$$ and asking her to generate $$$n$$$ terms of the sequence. More formally, Ryou wants Bocchi to generate the sequence $$$f_k$$$ defined by the recurrence relation $$$$$$f_1 = a; f_2 = b; f_k = f_{k - 1} + f_{k - 2} \, (2 \lt k \leq n).$$$$$$

But to really test if Bocchi is a Fibocchi master, she has added a twist! She wants Bocchi to answer $$$q$$$ queries regarding the sequence after performing some number of operations on it. An operation is defined by adding $$$1$$$ to $$$f_k$$$ for some $$$k$$$ $$$(1\leq k\leq n)$$$, then recalculating the recurrence starting from index $$$k + 1$$$.

For example, if $$$f = [2, 1, 3, 4, 7]$$$, Bocchi can apply an operation with $$$k = 3$$$, turning $$$f$$$ into $$$[2, 1, 4, 5, 9]$$$.

Note that if $$$k = 1$$$ is chosen, $$$f_2$$$ does not change.

Ryou will give Bocchi $$$q$$$ queries of the following form:

Given $$$a$$$ and $$$b$$$, find the minimum number of operations needed to make $$$\sum_{k = 1}^n f_k$$$ equal to $$$x$$$ or $$$-1$$$ if this is not possible.

Bocchi finds these advanced operations too difficult. Please help her prove her title as the Fibocchi master!

Input

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(3 \leq n \leq 30, 1 \leq q \leq 5 \cdot 10^5)$$$.

The next $$$q$$$ lines of each test case consist of $$$3$$$ integers $$$a, b, x$$$ $$$(1 \leq a, b \leq 10, 1 \leq x \leq 5 \cdot 10^6)$$$ — the queries.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

The test numbered $$$i$$$ satisfies $$$n = \max(3, \left \lfloor \frac{3i}{2} \right \rfloor)$$$.

Output

For each query, print one integer — the minimum number of operations needed to make $$$\sum_{k = 1}^n f_k$$$ equal to $$$x$$$ or $$$-1$$$ if this is not possible.

Example
Input
4 5
1 1 7
1 1 10
2 1 14
2 1 8
2 3 31
Output
0
1
1
-1
4
Note

In sample 1, the sequence is $$$[1,1,2,3]$$$, which already adds up to $$$7$$$, so no operations are needed.

In sample 2, the sequence is $$$[1,1,2,3]$$$. After an operation on index 1, the sequence turns into $$$[2, 1, 3, 4]$$$ which has a sum of $$$10$$$.

—

Problem Idea: training4usaco

Problem Preparation: HaccerKat

Occurrences: Novice H