Description
Solutions
Submission
Get Query Results

For a number N, a goodArray is the smallest possible array that consists of only powers of two (2^0, 2^1 ... 2^k) such that the sum of all the numbers in the array is equal to N.

For each query that consists of three integers l, r, and m, find out the product of elements goodArray[i] through goodArray[r] modulo m when goodArray is sorted in non-decreasing order.

Function Description

Complete the function getQueryResults in the editor.

getQueryResults has the following parameters:

  • long N: the integer N
  • int[][] queries: a 2D array of queries, each with 3 elements, l, r, and m.

    • Return

  • int[] answers: the answers to the queries

    • Example 1: 

    Input:  N = 26
    Output: [16, 1] 
    Explanation:
    

goodArray when sorted is [2, 8, 16].

For query l = 1, r = 2, m = 1009, ans = goodArray[1] * goodArray[2] = (2 * 8)modulo 1009 = 16.

For query l = 3, r = 3, m = 5, ans = goodArray3 = (16) modulo 5 = 1.

The answer is [16, 1].
    Constraints:
    • 1 <= N <= 1018
    • 1 <= q <= 105
    • 1 <= m <= 105
    • 1 <= l <= r <= |goodArray|, where |goodArray| denotes the length of array
    Testcase
    Result
    Case 1

    input:

    output: