a276. TOI 2022/05 潛力組：天空步道

題目描述

一條天空步道分成 N 段，每段高度是至少 1 的整數。相鄰兩段高度差不能超過 1，全部 N 段高度總和不能超過 M；最左端與最右端沒有必須降到 1 的限制。

現在要在第 K 段設置觀景台。對每筆詢問，請求出符合所有限制時，第 K 段最高可以多高。

輸入格式

第一行輸入詢問數 T，0 ≤ T ≤ 100000。 接下來 T 行各有 N、M、K，1 ≤ N ≤ M ≤ 1000000000，1 ≤ K ≤ N。

輸出格式

對每筆詢問輸出一行，內容為第 K 段的最大高度。T = 0 時不輸出任何內容。

來源

TOI 2022 年 5 月潛力組〈天空步道〉。依官方題意重新撰寫，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202205/Skywalk.pdf