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

1. \(N = 1\)인 경우: \(S_{N}\) = 1 (즉, 1 한 글자로 이루어진 문자열)
2. \(N \ge 2\)이고 N이 짝수인 경우: \(S_{N}\) = \(S_{⌊N/2⌋}\) 0 \(S_{⌊N/2⌋}\) (즉, 0 한 글자 좌우에 \(S_{⌊N/2⌋}\)가 이어진 문자열)
3. \(N \ge 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_{13}\) = 111011111110111이다.

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

q (\(1 \le q \le Q\))번째 질의는 세 개의 정수 (\(i_{q},j_{q},k_{q}\))가 주어질 때 다음과 같다: \(S_{N}[i_{q}\)..\(j_{q}\)]에서 0을 최대 \(k_{q}\)개까지 포함하는 가장 긴 부분문자열의 길이는?

위의 예에서 질의가 (1, 15, 0)이라면 가장 긴 부분문자열은 1로만 이루어져야 한다. 또, 질의가 \(S_{13}\) 전체에서 찾기를 요구하고 있으므로 해당 문자열의 길이는 7이다.

만약, (2, 14, 2)이라면 질의는 \(S_{13}\)의 두번째부터 14번째 문자까지에서 0이 최대 2개인 가장 긴 부분문자열을 찾으라고 요구한다. 그런데 \(S_{13}\)[2..14] = 1101111111011에는 0이 2개 뿐이므로 그 전체가 답이 되고, 그 길이는 13이다.

Hint.

부분문자열의 정의 길이가 l인 문자열 s와 \(1 \le i \le j \le 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 \le N \le 10^{18}\)
• \(1 \le Q \le 10\,000\)
• \(\sum_{q=1}^{Q} k_q \le 10\,000\). 즉, 모든 질의에서 주어지는 \(k\)의 값을 더하면 최대 \(10\,000\) 이다.
• 모든 \(1 \le q \le Q\) 에 대해, \(1 \le i_q \le j_q \le |S_N|\).

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

다음 Q개의 줄에 질의들이 한 줄에 하나씩 주어진다. 이 중 q (\(1 \le q \le Q\))번째 줄에는 세 개의 정수 \(i_{q},j_{q},k_{q}\)가 공백 하나씩을 사이로 두고 주어진다.

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

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2021 > 2차 대회 > 중등부 3번