CF1334D.Minimum Euler Cycle

You are given a complete directed graph $K_n$ with $n$ vertices: each pair of vertices $u \neq v$ in $K_n$ have both directed edges $(u, v)$ and $(v, u)$; there are no self-loops.

You should find such a cycle in $K_n$ that visits every directed edge exactly once (allowing for revisiting vertices).

We can write such cycle as a list of $n(n - 1) + 1$ vertices $v_1, v_2, v_3, \dots, v_{n(n - 1) - 1}, v_{n(n - 1)}, v_{n(n - 1) + 1} = v_1$ — a visiting order, where each $(v_i, v_{i + 1})$ occurs exactly once.

Find the lexicographically smallest such cycle. It's not hard to prove that the cycle always exists.

Since the answer can be too large print its $[l, r]$ segment, in other words, $v_l, v_{l + 1}, \dots, v_r$.

给你一个包含 $n$ 个顶点的完全有向图 $K_n$：对于 $K_n$ 中任意两个不同顶点 $u \neq v$，均同时存在有向边 $(u, v)$ 和 $(v, u)$；图中不含自环。

你需要在 $K_n$ 中找到一个遍历每条有向边恰好一次的环（允许重复访问顶点）。

这样的环可表示为一个长度为 $n(n - 1) + 1$ 的顶点序列 $v_1, v_2, v_3, \dots, v_{n(n - 1) - 1}, v_{n(n - 1)}, v_{n(n - 1) + 1} = v_1$ —— 即访问顺序，其中每条有向边 $(v_i, v_{i + 1})$ 恰好出现一次。

请找出字典序最小的此类环。可以证明，这样的环总是存在的。

由于答案可能过长，请仅输出其第 $[l, r]$ 段，即顶点序列 $v_l, v_{l + 1}, \dots, v_r$。

The first line contains the single integer $T$ ($1 \le T \le 100$) — the number of test cases.

Next $T$ lines contain test cases — one per line. The first and only line of each test case contains three integers $n$, $l$ and $r$ ($2 \le n \le 10^5$, $1 \le l \le r \le n(n - 1) + 1$, $r - l + 1 \le 10^5$) — the number of vertices in $K_n$, and segment of the cycle to print.

It's guaranteed that the total sum of $n$ doesn't exceed $10^5$ and the total sum of $r - l + 1$ doesn't exceed $10^5$.

第一行包含一个整数 $T$（$1 \le T \le 100$）—— 表示测试用例的数量。

接下来的 $T$ 行为测试用例，每行一个。每个测试用例所在行包含三个整数 $n$、$l$ 和 $r$（$2 \le n \le 10^5$，$1 \le l \le r \le n(n - 1) + 1$，$r - l + 1 \le 10^5$）—— 分别表示完全图 $K_n$ 的顶点数，以及需要输出的环上区间的左右端点。

保证所有测试用例中 $n$ 的总和不超过 $10^5$，且所有测试用例中 $r - l + 1$ 的总和也不超过 $10^5$。

For each test case print the segment $v_l, v_{l + 1}, \dots, v_r$ of the lexicographically smallest cycle that visits every edge exactly once.

对于每个测试用例，输出字典序最小的、恰好经过每条边一次的环路的子段 $v_l, v_{l + 1}, \dots, v_r$。

In the second test case, the lexicographically minimum cycle looks like: $1, 2, 1, 3, 2, 3, 1$.

In the third test case, it's quite obvious that the cycle should start and end in vertex $1$.

在第二个测试用例中，字典序最小的环为：$1, 2, 1, 3, 2, 3, 1$。

在第三个测试用例中，显然该环应从顶点 $1$ 开始并结束于顶点 $1$。