你各位知道，BK 跟 YP 分別是誰嘛？

BK ，身為 LYB 的專業真解王，是今年 IOICamp 負責講隨機、近似的講師。

YP ，身為 LYB 的假專業碼農，是今年 IOICamp 負責講根號算法的講師。

BK 非常喜歡堅果（因為堅果很好吃），而 YP 非常喜歡隨機（因為隨機很有趣）。

而且，在 LYB 的 ICPC 生涯中， YP 曾經用了被 BK 證明答對機率是百分之零的作法，AC 了一題 2018 年緬甸站的題目。從此之後........，就沒有從此之後了。

而當堅果遇上隨機，會產生出什麼新題目呢？

BK 和 YP 現在很衰的拿到了 ${10}^{18}$ 顆過期堅果 $1,2,\dots ,{10}^{18}$，第 $i$ 顆過期堅果的過期程度為 $i$ ，過期的日期也是 $i$ 。

雖然堅果很好吃，但如果 BK 和 YP 一口氣吃下了第 $a$ 天的過期堅果到第 $b$ 天的過期堅果，BK 和 YP 就會得到噁度 $a\oplus (a+1)\oplus \cdots \oplus b$ 。 $a\oplus b$ 代表 $a$ XOR $b$ 。注意到 BK 和 YP 吃下去的過期堅果過期的日期必須是連續的 。

而在接下來的 $Q$ 天， BK 和 YP 又要來決鬥了。在每次決鬥中， BK 和 YP 會先決定用第 $L$ 天的過期堅果到第 $R$ 天的過期堅果之間決鬥，以及一個噁心程度上限 $C$ 。BK 和 YP 希望在吃下去的堅果的噁心程度不超過 $C$ 的情況下，吃下盡量多的過期堅果。

正式的來說，你會有 $Q$ 組測試資料，每組測試資料會給你 $L,R,C$ ，請找到 $l,r$ ，滿足：

• $L\le l\le r\le R$
• $l\oplus (l+1)\oplus \cdots \oplus r\le C$
• $r-l+1$ 要盡可能的大