EOJ-自适应编程学习平台

奶龙国计划修建一张举世闻名的🐢速路网，连接全国的 $n$ 座城市。

然而，奶龙国的真实距离计算方式可不是普通的加减乘除，而是一种由奶龙科学家 sha7dow 发现的奇异规则：

当城市 $A$ 到 $B$ 的真实距离为 $s_1$，城市 $B$ 到 $C$ 的真实距离为 $s_2$ 时，奶龙们认为城市 $A$ 经过 $B$ 再到 $C$ 的真实距离并不是简单的 $s_1 + s_2$，而是：

其中，$s$ 是一个名为 sha7dow 常数 的宇宙极限值，而符号 $\land$ 表示 按位与（bitwise AND） 运算。

为了让全国的奶龙更容易进行计算，sha7dow 提出了一个聪明的概念——奶式距离：

如果一条道路的真实距离是 $d$，那么它的奶式距离定义为 $s - d$。

也就是说，奶式距离越大，说明两地的真实距离越短。

奶龙国的🐢速路网正一条条修建中，而奶龙市民们每天都好奇地打听：“从我家到那座城市，现在最短的路要多长呢？”

当然，他们问的其实是——两座城市之间的最长奶式距离！

你的任务是：在道路不断建成的过程中，实时回答奶龙市民们的询问。

第一行包含两个整数 $n$ 和 $q$，分别表示奶龙国的城市数量和事件数量，保证 $2 \leq n \leq 10^3$ 且 $1 \leq q \leq 10^6$。

接下来共有 $q$ 行，每行表示一个事件，格式如下：

• 若以 + 开头，后接三个整数 $u, v, w$，表示修建了一条连接城市 $u$ 和城市 $v$ 的🐢速路，其奶式距离为 $w$。保证 $1 \leq u, v \leq n$，$u \neq v$ 且 $0 \leq w < 2^{12}$。

• 若以 ? 开头，后接两个整数 $u, v$，表示一位奶龙市民询问城市 $u$ 与城市 $v$ 之间的最长奶式距离。保证 $1 \leq u, v \leq n$ 且 $u \neq v$。

对于每个 '?' 事件，输出一行一个整数，表示对应询问的答案（若两城市间不连通，则输出-1）。