22346번 - 일이 이어져야 좋다 서브태스크

양의 정수 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₁₃을 구해보면 다음과 같다.

• 위의 약속에서 적용이 가능한 것은 3번이므로 S₁₃ = S₆ 1 S₆임을 알수 있다.
• S₆은 위의 약속의 2번에 의해 S₃ 0 S₃이 되므로 S₁₃ = S₆ 1 S₆ = S₃ 0 S₃ 1 S₃ 0 S₃이다.
• S₃은 위의 약속의 3번과 1번을 순서대로 적용하면 111이 된다.
• 따라서 S₁₃ = 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이다.

첫 번째 줄에 N과 질의의 개수 Q가 정수로 주어진다.

다음 Q개의 줄에 질의들이 한 줄에 하나씩 주어진다. 이 중 q (1 ≤ q ≤ Q)번째 줄에는 세 개의 정수 i_q, j_q, k_q가 공백 하나씩을 사이로 두고 주어진다.

각 질의에 대한 답을 질의가 주어진 순서대로 각각 한줄에 하나씩 출력한다.

• 1 ≤ N ≤ 10¹⁸
• 1 ≤ Q ≤ 10 000
• ∑k_q ≤ 10 000 (1 ≤ q ≤ Q). 즉, 모든 질의에서 주어지는 k의 값을 더하면 최대 10 000이다.
• 모든 1 ≤ q ≤ Q에 대해, 1 ≤ i_q ≤ j_q ≤ (S_N의 길이)

부분문자열의 정의 길이가 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의 부분문자열이 아니다.