CF2086B Large Array and Segments

There is an array $ a $ consisting of $ n $ positive integers, and a positive integer $ k $ . An array $ b $ is created from array $ a $ according to the following rules: - $ b $ contains $ n \cdot k $ numbers; - the first $ n $ numbers of array $ b $ are the same as the numbers of array $ a $ , that is, $ b_{i} = a_{i} $ for $ i \le n $ ; - for any $ i > n $ , it holds that $ b_{i} = b_{i - n} $ . For example, if $ a = [2, 3, 1, 4] $ and $ k = 3 $ , then $ b = [2, 3, 1, 4, 2, 3, 1, 4, 2, 3, 1, 4] $ . Given a number $ x $ , it is required to count the number of such positions $ l $ ( $ 1 \le l \le n \cdot k $ ), for which there exists a position $ r \ge l $ , such that the sum of the elements of array $ b $ on the segment $ [l, r] $ is at least $ x $ (in other words, $ b_{l} + b_{l+1} + \dots + b_{r} \ge x $ ).

Each test consists of several test cases. The first line contains one integer $ t $ ( $ 1 \le t \le 10^{4} $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains three integers $ n $ , $ k $ , $ x $ ( $ 1 \le n, k \le 10^{5} $ ; $ 1 \le x \le 10^{18} $ ). The second line of each test case contains $ n $ integers $ a_{i} $ ( $ 1 \le a_{i} \le 10^{8} $ ). Additional constraints on the input: - the sum of $ n $ across all test cases does not exceed $ 2 \cdot 10^{5} $ ; - the sum of $ k $ across all test cases does not exceed $ 2 \cdot 10^{5} $ .

For each test case, output one integer — the number of suitable positions $ l $ in the array $ b $ .

In the first test case, the array $ b $ looks like this: $ $$$[3, 4, 2, 1, 5, 3, 4, 2, 1, 5, 3, 4, 2, 1, 5] $ $

There are $ 12 $ positions $ l $ for which there exists a suitable position $ r $ . Here are some (not all) of them:

• $ l = 1 $ , for which there is a position $ r = 6 $ , the sum over the segment $ \[1, 6\] $ equals $ 18 $ ;
• $ l = 2 $ , for which there is a position $ r = 5 $ , the sum over the segment $ \[2, 5\] $ equals $ 12 $ ;
• $ l = 6 $ , for which there is a position $ r = 9 $ , the sum over the segment $ \[6, 9\] $ equals $ 10$$$.