시간 제한메모리 제한제출정답맞은 사람정답 비율
5 초 (추가 시간 없음) 1024 MB78161225.532%

문제

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

  1. N = 1인 경우: SN = 1 (즉, 1 한 글자로 이루어진 문자열)
  2. N ≥ 2이고 N이 짝수인 경우: SN = S⌊N/2⌋ 0 S⌊N/2⌋ (즉, 0 한 글자 좌우에 S⌊N/2⌋가 이어진 문자열)
  3. N ≥ 2이고 N이 홀수인 경우: SN = S⌊N/2⌋ 1 S⌊N/2⌋ (즉, 1 한 글자 좌우에 S⌊N/2⌋가 이어진 문자열)

위의 약속에 따라 S13을 구해보면 다음과 같다.

  • 위의 약속에서 적용이 가능한 것은 3번이므로 S13 = S6 1 S6임을 알수 있다.
  • S6은 위의 약속의 2번에 의해 S3 0 S3이 되므로 S13 = S6 1 S6 = S3 0 S3 1 S3 0 S3이다.
  • S3은 위의 약속의 3번과 1번을 순서대로 적용하면 111이 된다.
  • 따라서 S13 = 111011111110111이다.

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

q (1 ≤ q ≤ Q)번째 질의는 세 개의 정수 (iq, jq, kq)가 주어질 때 다음과 같다: SN[iq..jq]에서 0을 최대 kq개까지 포함하는 가장 긴 부분문자열의 길이는?

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

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

입력

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

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

출력

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

제한

  • 1 ≤ N ≤ 1018
  • 1 ≤ Q ≤ 10 000
  • ∑kq ≤ 10 000 (1 ≤ q ≤ Q). 즉, 모든 질의에서 주어지는 k의 값을 더하면 최대 10 000이다.
  • 모든 1 ≤ q ≤ Q에 대해, 1 ≤ iq ≤ jq ≤ (SN의 길이)

서브태스크

번호 배점 제한
1 5

N = 2t가 성립하는 음이 아닌 정수 t가 존재한다. 즉, N은 1, 2, 4, 8, ..과 같이 2의 거듭제곱 중 하나이다.

2 11

N ≤ 1 000.

3 17

∑(jq − iq + 1) ≤ 100 000. 즉, 모든 질의에서 j − i + 1의 값을 더하면 최대 100 000이다.

4 25

모든 q (1 ≤ q ≤ Q)에 대해, kq = 0

5 42

추가 제약 조건 없음.

예제 입력 1

13 3
1 15 0
2 14 2
2 8 0

예제 출력 1

7
13
4

힌트

부분문자열의 정의 길이가 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이다. 따라서 0010101은 문자열 0100101의 부분문자열이다. 하지만 1010은 문자열 0100101의 부분문자열이 아니다.

채점 및 기타 정보

  • 예제는 채점하지 않는다.