CF1166D Cute Sequences

Given a positive integer $ m $ , we say that a sequence $ x_1, x_2, \dots, x_n $ of positive integers is $ m $ -cute if for every index $ i $ such that $ 2 \le i \le n $ it holds that $ x_i = x_{i - 1} + x_{i - 2} + \dots + x_1 + r_i $ for some positive integer $ r_i $ satisfying $ 1 \le r_i \le m $ . You will be given $ q $ queries consisting of three positive integers $ a $ , $ b $ and $ m $ . For each query you must determine whether or not there exists an $ m $ -cute sequence whose first term is $ a $ and whose last term is $ b $ . If such a sequence exists, you must additionally find an example of it.

N/A

N/A

Consider the sample. In the first query, the sequence $ 5, 6, 13, 26 $ is valid since $ 6 = 5 + \bf{\color{blue} 1} $ , $ 13 = 6 + 5 + {\bf\color{blue} 2} $ and $ 26 = 13 + 6 + 5 + {\bf\color{blue} 2} $ have the bold values all between $ 1 $ and $ 2 $ , so the sequence is $ 2 $ -cute. Other valid sequences, such as $ 5, 7, 13, 26 $ are also accepted. In the second query, the only possible $ 1 $ -cute sequence starting at $ 3 $ is $ 3, 4, 8, 16, \dots $ , which does not contain $ 9 $ .