일이 이어져야 좋다

양의 정수 $N$으로 문자열 $S_N$을 다음과 같이 정의한다. $\lfloor N/2 \rfloor$은 $N$을 2로 나눈 몫이다.

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

$S_{13}$은 다음과 같이 만들어진다.

• 3번 규칙이 적용되므로 $S_{13} = S_6 1 S_6$이다.
• 2번 규칙에 따라 $S_6$은 $S_3 0 S_3$이 되므로 $S_{13} = S_3 0 S_3 1 S_3 0 S_3$이다.
• 3번 규칙과 1번 규칙을 차례로 적용하면 $S_3 = 111$이 된다.
• 따라서 $S_{13} = 111011111110111$이다.

양의 정수 $N$이 주어질 때, 다음 형태의 질의 $Q$개를 해결하는 프로그램을 작성하라. $q$번째 질의는 정수 세 개 $(i_q, j_q, k_q)$가 주어진다. 이때 $S_N[i_q..j_q]$에서 0을 최대 $k_q$개까지 포함하는 부분문자열 중 가장 긴 것의 길이를 구한다.

질의 $(1, 15, 0)$이면 0을 포함하지 않는 부분문자열을 찾아야 하므로 답은 7이다. 질의 $(2, 14, 2)$이면 $S_{13}[2..14] = 1101111111011$에는 0이 2개뿐이므로 구간 전체가 답이 되고, 그 길이는 13이다.

첫 번째 줄에 정수 $N$과 $Q$가 주어진다. 다음 $Q$개의 줄에는 각각 $i_q$, $j_q$, $k_q$가 공백 하나씩을 사이에 두고 주어진다.

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

$1 \le N \le 10^{18}$

$1 \le Q \le 10\,000$

모든 질의의 $k_q$를 더하면 $10\,000$을 넘지 않는다.

모든 $1 \le q \le Q$에 대해 $1 \le i_q \le j_q \le$ ($S_N$의 길이)이다.

길이 $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은 부분문자열이 아니다.