일이 이어져야 좋다

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

1. $ N = 1 $인 경우: $ S_N = 1 $ (즉, $ 1 $ 한 글자로 이루어진 문자열)
2. $ N \ge 2 $이고 $ N $이 짝수인 경우: $ S_N = S_{\lfloor N/2\rfloor}\ 0\ S_{\lfloor N/2\rfloor} $ (즉, $ 0 $ 한 글자 좌우에 $ S_{\lfloor N/2\rfloor} $가 이어진 문자열)
3. $ N \ge 2 $이고 $ N $이 홀수인 경우: $ S_N = S_{\lfloor N/2\rfloor}\ 1\ S_{\lfloor N/2\rfloor} $ (즉, $ 1 $ 한 글자 좌우에 $ S_{\lfloor N/2\rfloor} $가 이어진 문자열)

위의 약속에 따라 $ 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 $이다.

부분문자열의 정의

​ 길이가 $ 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 $의 길이)

1. (5점) $ N=2^t $가 성립하는 음이 아닌 정수 $ t $가 존재한다. 즉, $ N $은 1, 2, 4, 8, ..과 같이 2의 거듭제곱 중 하나이다.
2. (11점) $ N\le 1\,000 $.
3. (17점) $ \sum_{q=1}^{Q} (j_q - i_q + 1) \le 100\,000 $. 즉, 모든 질의에서 $ j-i+1 $의 값을 더하면 최대 $ 100\,000 $이다.
4. (25점) 모든 $ q $ ($ 1 \le q \le Q $)에 대해, $ k_q = 0 $
5. (42점) 추가 제약 조건 없음.

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

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

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