AT_arc210_e [ARC210E] Subset Sum Gaps

You are given a sequence of positive integers $ A=(A_1,A_2,\ldots,A_N) $ . There are $ 2^N $ subsequences of $ A $ when distinguishing subsequences by the indices of their elements. Let $ S_1, S_2, \ldots, S_{2^N} $ be the sums of these subsequences, enumerated **in ascending order**. For all integers $ k $ ( $ 1\leq k\leq 2^N-1 $ ) that satisfy $ 1.01 \times S_k\leq S_{k+1} $ , output $ S_k, S_{k+1}, (k\bmod 998244353) $ . What is a subsequenceA subsequence of a sequence $ A $ is a sequence obtained by removing zero or more elements from $ A $ and arranging the remaining elements in their original order.

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

On the first line, output the number of integers $ k $ that satisfy the condition. From the second line onwards, for each integer $ k $ that satisfies the condition, output $ S_k, S_{k+1}, (k\bmod 998244353) $ separated by spaces on each line. Output in ascending order of $ k $ .

### Sample Explanation 1 We have the following eight subsequences: - The empty subsequence. The sum is $ 0 $ . - $ (5) $ . The sum is $ 5 $ . This subsequence appears twice. - $ (3) $ . The sum is $ 3 $ . - $ (5,5) $ . The sum is $ 10 $ . - $ (5,3) $ . The sum is $ 8 $ . This subsequence appears twice. - $ (5,5,3) $ . The sum is $ 13 $ . $ S_1, S_2, \ldots, S_8 $ are $ 0,3,5,5,8,8,10,13 $ in order. ### Constraints - $ 2\leq N\leq 5000 $ - $ 1\leq A_i\leq 10^{13} $