← 返回题目列表

Codeforces · 1379/B

B. 可疑的加密货币

中文机器翻译题面 查看原题

Pasha 喜欢向他的朋友发送严格的正整数。 Pasha 关心安全性,因此当他想要发送一个整数 $$$n$$$ 时,他会通过以下方式对其进行加密:他选择三个整数 $$$a$$$、$$$b$$$ 和 $$$c$$$ 使得 $$$l \leq a,b,c \leq r$$$,然后计算加密值 $$$m = n \cdot a + b - c$$$。

不幸的是,对手拦截了 $$$l$$$、$$$r$$$ 和 $$$m$$$ 值。是否可以从这些信息中恢复 $$$a$$$、$$$b$$$ 和 $$$c$$$ 的原始值?更正式地说,您需要找到 $$$a$$$、$$$b$$$ 和 $$$c$$$ 的任意值,使得

- $$$a$$$、$$$b$$$ 和 $$$c$$$ 是整数,
- $$$l \leq a, b, c \leq r$$$,
- 存在一个严格正整数 $$$n$$$,使得 $$$n \cdot a + b - c = m$$$。

输入

第一行包含唯一的整数 $$$t$$$ ($$$1 \leq t \leq 20$$$) — 测试用例的数量。以下 $$$t$$$ 行每行描述一个测试用例。

每个测试用例由三个整数 $$$l$$$、$$$r$$$ 和 $$$m$$$ ($$$1 \leq l \leq r \leq 500\,000$$$、$$$1 \leq m \leq 10^{10}$$$) 组成。这些数字表明问题的答案是存在的。

输出

对于每个测试用例,输出三个整数 $$$a$$$、$$$b$$$ 和 $$$c$$$,使得 $$$l \leq a, b, c \leq r$$$ 并且存在严格正整数 $$$n$$$,使得 $$$n \cdot a + b - c = m$$$。保证至少有一种可能的解,如果有多种解则可以输出任意可能的组合。

示例

输入 #1

2
4 6 13
2 3 1

输出 #1

4 6 5
2 2 3

注意

在第一个示例中 $$$n = 3$$$ 是可能的,然后 $$$n \cdot 4 + 6 - 5 = 13 = m$$$。其他可能的解决方案包括:$$$a = 4$$$、$$$b = 5$$$、$$$c = 4$$$(当$$$n = 3$$$时); $$$a = 5$$$,$$$b = 4$$$,$$$c = 6$$$(当$$$n = 3$$$时); $$$a = 6$$$,$$$b = 6$$$,$$$c = 5$$$(当$$$n = 2$$$时); $$$a = 6$$$,$$$b = 5$$$,$$$c = 4$$$(当$$$n = 2$$$时)。

在第二个示例中,唯一可能的情况是 $$$n = 1$$$:在这种情况下 $$$n \cdot 2 + 2 - 3 = 1 = m$$$。请注意,$$$n = 0$$$ 是不可能的,因为在这种情况下$$$n$$$ 不是严格的正整数。