Patisserie ABC 2

题目描述

Takahashi，作为 ABC Confiserie 的糕点师，决定制作蛋糕来庆祝 AtCoder Beginner Contest 200。 Takahashi 制作的每个蛋糕有三个参数：beauty、taste 和 popularity，每个参数都表示为介于 $1$ 到 $N$（含）之间的整数。 他为每个三元组 $(i,j,k)\ (1 \le i,j,k \le N)$ 制作了一个美为 $i$、味为 $j$、受欢迎度为 $k$ 的蛋糕。
然后，他按如下方式将这 $N^3$ 个蛋糕排成一行：

蛋糕按美、味、受欢迎度之和从左到右按升序排列。 对于两个具有相同美、味、受欢迎度之和的蛋糕，较小美值的蛋糕在左侧。 对于两个具有相同和且相同美值的蛋糕，较小味值的蛋糕在左侧。

求从左数第 $K$ 个蛋糕的美、味、受欢迎度。

输入格式

输入按照下述格式从标准输入给出： $N$ $K$

输出格式

以空格分隔的顺序打印表示该蛋糕的美、味、受欢迎度的三个整数。

2 5

1 2 2

1000000 1000000000000000000

1000000 1000000 1000000

9 47

3 1 4

提示

输入中的所有值均为整数。 $1 \le N \le 10^6$ $1 \le K \le N^3$蛋糕的顺序如下： $(1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,2,2),(2,1,2),(2,2,1),(2,2,2)$。 这里，每个三元组整数表示一个蛋糕的美、味、受欢迎度。
输入的值可能很大。

标签: AtCoder|abc200E

来源

AtCoder|abc200E