CF840E In a Trap

Lech got into a tree consisting of $ n $ vertices with a root in vertex number $ 1 $ . At each vertex $ i $ written integer $ a_{i} $ . He will not get out until he answers $ q $ queries of the form $ u $ $ v $ . Answer for the query is maximal value  among all vertices $ i $ on path from $ u $ to $ v $ including $ u $ and $ v $ , where $ dist(i,v) $ is number of edges on path from $ i $ to $ v $ . Also guaranteed that vertex $ u $ is ancestor of vertex $ v $ . Leha's tastes are very singular: he believes that vertex is ancestor of itself. Help Leha to get out. The expression  means the bitwise exclusive OR to the numbers $ x $ and $ y $ . Note that vertex $ u $ is ancestor of vertex $ v $ if vertex $ u $ lies on the path from root to the vertex $ v $ .

First line of input data contains two integers $ n $ and $ q $ ( $ 1

Output $ q $ lines — answers for a queries.