/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
「ABC洋菓子店」で働くパティシエである高橋君は、ケーキを作って AtCoder Beginner Contest 200 を祝うことにしました。
高橋君の作るケーキは、「綺麗さ」「おいしさ」「人気度」の 3 つのパラメータをもち、それぞれのパラメータは 1 以上 N 以下の整数で表されます。
高橋君は、「綺麗さ」が i 、「おいしさ」が j 、「人気度」が k であるケーキを、全ての組 (i,j,k)\ (1 \le i,j,k \le N) に対して 1 つずつ作りました。
その後、高橋君は、できた N^3 個のケーキを以下の順序で並べました。
- 「綺麗さ」+「おいしさ」+「人気度」が小さいものを、より左に並べる。
- ここまでで順序がつかなければ、「綺麗さ」が小さいものを、より左に並べる。
- ここまでで順序がつかなければ、「おいしさ」が小さいものを、より左に並べる。
このとき、左から K 番目にあるケーキの各パラメータの値を求めてください。
制約
- 入力は全て整数
- 1 \le N \le 10^6
- 1 \le K \le N^3
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
答えを「綺麗さ」「おいしさ」「人気度」の順に空白区切りで 3 つの整数として出力せよ。
入力例 1
2 5
出力例 1
1 2 2
各ケーキの各パラメータの値を (「綺麗さ」,「おいしさ」,「人気度」) と書くと、ケーキは左から以下の順に並びます。
(1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,2,2),(2,1,2),(2,2,1),(2,2,2)
入力例 2
1000000 1000000000000000000
出力例 2
1000000 1000000 1000000
入力される値が大きくなることもあります。
入力例 3
9 47
出力例 3
3 1 4
Score : 500 points
Problem Statement
Takahashi, a pastry chef at ABC Confiserie, has decided to make cakes to celebrate AtCoder Beginner Contest 200.
A cake made by Takahashi has three parameters: beauty, taste, and popularity, each of which is represented by an integer between 1 and N (inclusive).
He has made a cake of beauty i, taste j, and popularity k for every triple (i,j,k)\ (1 \le i,j,k \le N).
Then, he has arranged these N^3 cakes in a row, as follows:
- The cakes are in ascending order of sum of beauty, taste, and popularity from left to right.
- For two cakes with the same sum of beauty, taste, and popularity, the cake with the smaller beauty is to the left.
- For two cakes with the same sum and the same beauty, the cake with the smaller taste is to the left.
Find the beauty, taste, and popularity of the K-th cake from the left.
Constraints
- All values in input are integers.
- 1 \le N \le 10^6
- 1 \le K \le N^3
Input
Input is given from Standard Input in the following format:
N K
Output
Print three integers representing the cake's beauty, taste, popularity, in this order, with spaces in between.
Sample Input 1
2 5
Sample Output 1
1 2 2
The cakes are in the following order:
(1,1,1),(1,1,2),(1,2,1),(2,1,1),(1,2,2),(2,1,2),(2,2,1),(2,2,2).
Here, each triple of integers represents the beauty, taste, and popularity of a cake.
Sample Input 2
1000000 1000000000000000000
Sample Output 2
1000000 1000000 1000000
The values in input may be large.
Sample Input 3
9 47
Sample Output 3
3 1 4