題目描述

因評測機性能差異，本題每個測試點時限有調整。

解決 高樓 (buildings) 這個問題後，在你的幫助下，小 P 也總算學會了如何計算一個序列的最大值與嚴格次大值。現在，他囂張地向你發起挑戰，若你能快速解決他提出的問題，你將會獲得豐富的獎品。
這項挑戰被分為兩個階段。
在第一個階段中，你需要構造一個長度為 n 的整數序列 a。小 P 會給你三個正整數 n,m,s，你需要根據 s 的值計算序列 a 所有的元素。具體地，它的第 i 個元素 a[i] 的值可以用以下式子表示：

其中，mod 是取餘運算，a mod b 即為 a 除以 b 所得的餘數。
在第二個階段中，小 P 會問你一些問題以驗證你構造序列的正確性。具體地：
• 若 m=1，你需要回答這個序列的最小值、嚴格次小值、嚴格第三小值、最大值、嚴格次大值和嚴格第三大值。
• 其中，嚴格次小值是指在序列中數值比最小值大的元素當中的最小值；而嚴格第三小值是指在序列中數值比嚴格次小值大的元素當中的最小值。
• 類似地，嚴格次大值是指在序列中數值比最大值小的元素當中的最大值；而嚴格第三大值是指在序列中數值比嚴格次大值小的元素當中的最大值。
• 若 m=2，你需要把這個序列從小到大排序。記排序後的結果為 a'，則你需要回答 a'[1],a'[2],a'[3],a'[n],a'[n-1],a'[n-2] 的值。
• 若 m=3，你需要找出兩個滿足 1≤l<r≤n 且 r-l=⌊√n-1⌋ 的整數 l,r，使得 a[l]+a[l+1]+a[l+2]+⋯+a[r] 的值最大。特別地，你只需要回答這個最大值。

輸入格式

你需要在標準輸入 (stdin) 讀入數據。
輸入僅有一行，包含三個正整數 n,m,s，以空格分隔。

輸出格式

你需要在標準輸出 (stdout) 輸出答案。
• 若 m=1，輸出一行，六個整數依次表示序列的最小值、嚴格次小值、嚴格第三小值、最大值、嚴格次大值和嚴格第三大值，以空格分隔。
• 若 m=2，輸出一行，六個整數依次表示 a[1],a[2],a[3],a[n],a[n-1],a[n-2] 的值，以空格分隔。
• 若 m=3，輸出一行，一個整數表示答案。

Samples

["5 1 13","5 3 13"]

["13 26 39 143 78 39","221"]

提示

【樣例1 解釋】
構造後的序列 a=(13,26,78,143,39)。
易得最小值為 13，嚴格次小值為 26，嚴格第三小值為 39，最大值為 143，嚴格次大值為 78，嚴格第三大值為 39。

【數據範圍】
對於所有測試數據，保證：
• n≤10⁸
• m≤3
• s≤4×10⁵
• 對於給定的詢問，存在一個數值滿足對應的條件。

原始資料

• Zero1 題號：b599
• Hydro 題號：Z1599
• Locale：zh_TW
• Display：open