我常常追忆过去。
虽然，过去的棱角曾深深创伤了我……
当我顺着时间的长河而上时，我看到那些令我窒息的过往，重新定格在脑海，化作天上的朵朵白云。
我看到一棵树，随着时间的流逝伸展枝桠，在变化的点权中追寻着一棵树的价值……
我看到一家店，里面的人在思考，思考在清仓甩卖糖果时收益最大的标价方案……
我看到一个人，正自顾自地玩着谐音替换的游戏，即使不小心加多或减少了几个字符也乐此不疲……
我看到一座城，这里刚刚被灾害侵袭，正在进行紧张的道路修复工作……
我看到一段过往，纵使曾经令我彻夜难眠，但心中的创伤被时间抚平后，终于能看清它们在岁月的长河里熠熠生辉……
最后，当我走到时间的起点，追忆之旅的尽头，我看到了我，那个从联合省选 2025 考场上走出来的我。
我看到了他脸上的无奈……
我听到他对我说……
或者，我希望有一天，他能笑着对我说……
“我常常追忆过去。”
这是一道交互题。
这是这个问题的困难版本。两个版本的不同之处在于，本题中你有 次“追忆”的机会。
有一张 个点 条边的无向连通图（边权均为 ），不幸的是，你忘记了 到 之间的最短路。
你有 次“追忆”的机会，每次“追忆”，你可以想起两个点之间的最短路长度。
由于你实在想不起 到 的最短路长度了，你需要在不直接“追忆” 到 之间的最短路的情况下，求出 到 的最短路。
但是，追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。为了满足你对美的苛求，在本题中，你的输出与标准答案的差的绝对值不超过 即视为通过。
交互格式
首先你可以读入一个正整数 ，表示点的个数，注意：你无法读入也不需要读入边数 ！
当你想要“追忆”时，输出一行 ? x y 表示询问 至 的最短路长度，你需要保证 且 。若你的询问不符合上述要求或询问次数超过 ，交互库会返回 WA，否则交互库会输出一个正整数表示最短路长度。
当你确定了答案时，可以输出一行 ! x 表示你求出的答案，若你的答案与标准答案相差不超过 ，交互库会返回 AC，否则交互库会返回 WA。
