양의 정수 N으로 만들어지는 문자열 S_N은 다음과 같이 정의된다. 아래에서 ⌊N/2⌋은 N을 2로 나눈 몫이다.

1. N = 1인 경우: S_N = 1 (즉, 1 한 글자로 이루어진 문자열)

2. N ≥ 2이고 N이 짝수인 경우: S_N = S_{⌊N/2⌋} 0 S_{⌊N/2⌋} (즉, 0 한 글자 좌우에 S_{⌊N/2⌋}가 이어진 문자열)

3. N ≥ 2이고 N이 홀수인 경우: S_N = S_{⌊N/2⌋} 1 S_{⌊N/2⌋} (즉, 1 한 글자 좌우에 S_{⌊N/2⌋}가 이어진 문자열)

위의 약속에 따라 S_{13}을 구해보면 다음과 같다.

• 위의 약속에서 적용이 가능한 것은 3번이므로 S_{13} = S_6 1 S_6임을 알수 있다.

• S_6은 위의 약속의 2번에 의해 S_3 0 S_3이 되므로 S_{13} = S_6 1 S_6 = S_3 \, 0 \, S_3 \, 1 \, S_3 \, 0 \, S_3이다.

• S_3은 위의 약속의 3번과 1번을 순서대로 적용하면 111이 된다.

• 따라서 S_3 = 111011111110111이다.

양의 정수 N이 주어질 때, 아래와 같은 형태의 질의 Q개를 해결하는 프로그램을 작성하라.

q (1 ≤ q ≤ Q)번째 질의는 세 개의 정수 (i_q, j_q, k_q)가 주어질 때 다음과 같다:

S_N [i_q..j_q]에서 0을 최대 k_q개까지 포함하는 가장 긴 부분문자열의 길이는?

위의 예에서 질의가 (1, 15, 0)이라면 가장 긴 부분문자열은 1로만 이루어져야 한다.

또, 질의가 S₁₃ 전체에서 찾기를 요구하고 있으므로 해당 문자열의 길이는 7이다.

만약, (2, 14, 2)이라면 질의는 S₁₃의 두번째부터 14번째 문자까지에서 0이 최대 2개인 가장 긴 부분문자열을 찾으라고 요구한다.

그런데 S₁₃[2..14] = 1101111111011에는 0이 2개 뿐이므로 그 전체가 답이 되고, 그 길이는 13이다.

참고

부분문자열의 정의 길이가 l 인 문자열 s와 1 ≤ i ≤ j ≤ l 인 두 정수 i와 j에 대해, s[i..j]는 s의 i번째

문자에서부터 j번째 문자까지를 모두 순서대로 포함하는 문자열이며,

이러한 문자열들을 문자열 s의 부분문자열이라고 한다.

예를 들어 s가 0100101이라면, s[3..5]는 001이고, s[4..7]은 0101이다. 따라서 001과 0101은 문자열

0100101의 부분문자열이다. 하지만 1010은 문자열 0100101의 부분문자열이 아니다.

제약 조건

• 1 ≤ N ≤ 10^{18}

• 1 ≤ Q ≤ 10,000

• \textstyle \sum^Q_{q=1} k_q \le 10,000. 즉, 모든 질의에서 주어지는 k의 값을 더하면 최대 10,000이다.

• 모든 1 ≤ q ≤ Q에 대해, 1 ≤ i_q ≤ j_q ≤ (S_N의 길이)

일이 이어져야 좋다 timer 5초 memory 1024MB

일이 이어져야 좋다 5초 1024MB