Inspiration

LiChao loves powers of 2 and wants to create a programming problem inspired by them. After accidentally leaking his last problem (Transit) at AIIO of which he also threw extremely hard, he needs new inspiration. The metro is under maintenance, but LiChao has a teleporter. There are $N$ stations, each with an inspiration value $A_i$. Each station provides inspiration from the powers of 2 that make up its inspiration value. LiChao would go on $Q$ inspiration gathering journeys, but he is rather forgetful and would forget if he stops seeing a number at each station he walks to. LiChao knows this so he sets goals for himself on each journey. He would like to end his journey with at least $K_j$ inspiration from numbers, and he would walk as far as he can on each journey.

On each journey:

• He teleports to a starting station $S_j$ and gains inspiration from the powers of 2 that make up the inspiration value of that station. For example, a station with an inspiration value of 11 would give him inspiration from 3 numbers: 8, 2, and 1.
• He walks through stations one by one, since he needs to touch grass.
• When LiChao walks to the next station, he would lose inspiration from a number if the station he walks to doesn’t give him inspiration from that number. Suppose LiChao has inspiration from the numbers 8, 2, and 1 and he walks to a station with inspiration value 13, which gives him inspiration from the numbers 8, 4, and 1. LiChao won’t forget the numbers 8 and 1, but he will forget the number 2 since it's not given to him at the station he walked to.
• He must return home if he reaches the last station ($N$) or if going to the next station leaves him with less than $K_j$ numbers.
• Since he would get bored if he takes inspiration from the same number from the same station in quick succession, the numbers LiChao ended up with at the end of his journey won't be available from any of the stations he visited on this current journey for the next $B_j$ journeys.

Note

• This problem may not be fully solvable in an interpretered language, a compiled language such as C++ is recommended.
• Make sure to use a 64-bit integer type to avoid integer overflow.

Input

• The first line will contain $N$, the number of stations.
• The next line will contain $N$ space-separated integers, $A_1, A_2, A_3, \ldots, A_N$.
• The next line will contain $Q$, the number of journeys.
• The following $Q$ lines will each contain 3 space-separated numbers $S_j$, $K_j$, and $B_j$.

Output

• Output $Q$ lines, each containing the maximum distance LiChao can walk in each of his journeys.

Constraints

• $1 \le N, Q \le 2 \cdot 10^5$
• $0 \le A_i \le 2^{51}-1$
• $1 \le S_j \le N$
• $0 \le B_j \le Q$
• $1 \le K_j \le 50$
• $K_j \le$ The initial numbers of inspiration gained from station $S_j$ for all queries even if some numbers of inspiration aren’t available due to previous queries.

Subtasks

• Subtask 1 (35%): $B_j = Q$, $N, Q \le 5 \cdot 10^4$
• Subtask 2 (35%): $B_j = 0$, $N, Q \le 5 \cdot 10^4$
• Subtask 3 (20%): $N, Q \le 5 \cdot 10^4$
• Subtask 4 (10%): No further constraints

Sample Explanation

In sample 1, LiChao starts at station 2 and gains inspiration from 8, 2, and 1. He can walk to station 3 since it gives him inspiration from 8, 4, and 1. LiChao will forget the number 2 but he still has inspiration from 2 numbers. He would then walk to station 4 leaving him with inspiration from 8 and 1. He won't be able to walk to station 5 since it only gives him inspiration from 8 and 2, so he would forget the number 1 and leave him with only number 8. So the latest he can leave is at station 4, so he can walk at most twice. When LiChao returns home from his first journey, stations 2, 3, and 4 would no longer give him inspiration from the numbers 8 and 1 for the next 5 journeys.

On his second journey, LiChao starts at station 1, giving him numbers 2 and 1. He can walk to station 2, leaving him with only number 2 since he can't gain inspiration from 8 or 1 from this station due to his first journey. He would forget all numbers if he goes to station 3 since it only gives him the number 4 due to the first journey, so he can walk at most once. When LiChao returns home from his second journey, stations 1 and 2 would no longer give him inspiration from the number 2 for the next 5 journeys.

On his third journey, LiChao starts at station 1, giving him number 1 since he can't get 2 from that station due to his second journey. He can't walk to station 2 since 8, 2, and 1 are still unusable due to previous journeys. When he leaves, station 1 will no longer give him the number 1 for the next 5 journeys.

In sample 2, the first journey is the same as sample 1, but in journey 2, LiChao is already not bored with the numbers he left with in his first journey. He starts with the numbers 2 and 1, then goes to station 2 and keeps both of his numbers, then he goes to station 3 losing the number 2 leaving him with only the number 1. Then he goes to station 4 with just the number 1. Going to station 5 will cause him to forget number 1 since it only gives him 8 and 2, so he has to end his journey at station 4 taking 3 walks. The third journey is identical to the second journey.

In sample 3, everything up to and including the second journey is the same as sample 1. But in journey 3, the numbers 8 and 1 are available again from stations 2, 3, and 4 since they were unavailable for 1 journey after his first journey. LiChao starts at station 1 with the number 1, station 2 gives him 8 and 1 since 2 is still not available, he will end up with 1. He then is able to visit station 3 which gives him 8, 4, and 1, leaving him with still just 1. He then will visit station 4 which gives him 8, 2, and 1, still leaving him with 1. Station 5 only gives him 8 and 2 so he can't go there and has to end his journey at station 4 making 3 walks.