「咚！！」 勇者帥氣地推開大門，準備跟魔王拼命。
正當勇者的劍準備出鞘，勇者定神一看……「咦！怎麼魔王的等級比我高了10倍！」
這完完全全沒有道理，畢竟勇者已經達成所有條件，獲得了理論上最強的技能了。
「嘖！這遊戲一定不是設計給人過關的！」勇者憤怒道。

不論如何，現在最重要的事情就只有逃命了。

要知道，魔王房間對外的通道只有由$N$根石柱由內往外排成一直線的道路，剩下的地方都被岩漿所包圍。石柱由內而外從1編號到$N$，編號為$i$的石柱的位置為$x_i$。勇者從最內側的石柱出發，藉由不斷的往外跳到另一根石柱（一次可以跳過任意根石柱，但不能往內跳），最終抵達最外側的石柱以逃出魔王房間。這$N$根石柱的高度都不同，而這是有用意的：愈高的石柱會愈受到魔王的魔力影響，所以勇者就需要耗費愈多的魔力才能在其上跳躍。當然，兩個石柱之間距離愈遠，勇者也會需要花費愈多的魔力進行跳躍。如果兩個石柱$A,B$之間的距離是$d$（也就是兩個石柱位置的差），而兩個石柱的高度分別為$a,b$，那麼勇者就需要耗費$(10^ 5+1)(a+b+d)$的魔力才能從$A$跳到$B$。

然而，這個勇者不是普通的勇者。他有一個特殊技能：所耗費的魔力可以轉換成怒氣值，使之後的移動可以更不耗費魔力。具體來說，勇者的怒氣值是一個$0$到$10^ 5$的整數。如果勇者在跳躍當下的怒氣值是$C$，那麼他只需要$(10^ 5+1-C)(a+b+d)$的魔力就可以進行上述的跳躍。而跳躍所花費的魔力會在跳躍完成後轉換為怒氣值：如果勇者從開始逃命到當前所花費的總魔力是$p$，那麼他的怒氣值就會變成$\min\left(10^ 5,\left\lfloor \sqrt[3]{p}\right\rfloor\right)$。

然而，這個勇者是個高傲的勇者，因此他連逃命都想要展示他高超的路徑規劃能力。具體來說，他的路徑會滿足，對於所有途中經過的石柱，他抵達該石柱所用的魔力都要愈小愈好。當然這裡的「愈小愈好」是有條件的：如果對於某個石柱$X$，有某條起點到$X$的路徑$S$所耗費的魔力並非最小，那麼所有以$S$開頭的路徑都不會被考慮。
（例如，如果$1 \rightarrow 2 \rightarrow 3$耗費的魔力值大於$1\rightarrow 3$，那麼就算$1\rightarrow 2\rightarrow 3\rightarrow 4$耗費的魔力值小於$1\rightarrow 3\rightarrow 4$，勇者仍然不會選擇$1\rightarrow 2\rightarrow 3\rightarrow 4$這條路徑。）

你，身為勇者的競爭者，對勇者這樣高傲的行為感到十分不悅，因此你決定在他逃命的途中偷襲他。所以，你得先寫個程式，算出一條勇者可能採用的路徑。