Code Festival Team Relay (Parallel) - Evergrowing Tree

You are given an integer N. Consider an infinite N-ary tree as shown below:

<image>

Figure: an infinite N-ary tree for the case N = 3

As shown in the figure, each vertex is indexed with a unique positive integer, and for every positive integer there is a vertex indexed with it. The root of the tree has the index 1. For the remaining vertices, vertices in the upper row have smaller indices than those in the lower row. Among the vertices in the same row, a vertex that is more to the left has a smaller index.

Regarding this tree, process Q queries. The i-th query is as follows:

* Find the index of the lowest common ancestor (see Notes) of Vertex v_i and w_i.

Constraints

* 1 ≤ N ≤ 10^9
* 1 ≤ Q ≤ 10^5
* 1 ≤ v_i < w_i ≤ 10^9

Input

Input is given from Standard Input in the following format:


N Q
v_1 w_1
:
v_Q w_Q


Output

Print Q lines. The i-th line (1 ≤ i ≤ Q) must contain the index of the lowest common ancestor of Vertex v_i and w_i.

Examples

Input

3 3
5 7
8 11
3 9


Output

2
1
3


Input

100000 2
1 2
3 4


Output

1
1

Source: atcoder | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
(N, Q) = map(int, input().split())
vws = [tuple(map(int, input().split())) for _ in range(Q)]
anss = []
if N == 1:
	anss = [min(v, w) for (v, w) in vws]
else:
	for (v, w) in vws:
		(v, w) = (v - 1, w - 1)
		while v != w:
			if v > w:
				v = (v - 1) // N
			else:
				w = (w - 1) // N
		anss.append(v + 1)
print('\n'.join(map(str, anss)))


(n, q, *t) = map(int, open(0).read().split())
for (v, w) in zip(t[::2], t[1::2]):
	if n < 2:
		print(min(v, w))
		continue
	(s, t) = (set(), set())
	while v:
		s |= {v}
		v = (v + n - 2) // n
	while w:
		t |= {w}
		w = (w + n - 2) // n
	print(max(s & t))


import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
ans = ''
(n, q) = [int(item) for item in input().split()]
if n == 1:
	for i in range(q):
		(v, w) = [int(item) for item in input().split()]
		print(min(v, w))
	exit()
for i in range(q):
	(v, w) = [int(item) - 1 for item in input().split()]
	while v != w:
		if v > w:
			v = (v - 1) // n
		else:
			w = (w - 1) // n
	print(v + 1)


(N, Q) = map(int, input().split())
if N == 1:
	for i in range(Q):
		print(min(map(int, input().split())))
	exit()

def solve(s):
	(a, b) = map(int, s.split())
	while a != b:
		if a < b:
			(a, b) = (b, a)
		a = (a + N - 2) // N
	return str(a)
print('\n'.join(map(solve, [input() for i in range(Q)])))


(n, q) = map(int, input().split())
if n == 1:

	def solve(v, w):
		return min(v, w)
else:

	def solve(v, w):
		while v != w:
			if v > w:
				(v, w) = (w, v)
			w = (w + n - 2) // n
		return v
print('\n'.join(map(str, (solve(*map(int, input().split())) for _ in range(q)))))


(n, q) = map(int, input().split())
if n == 1:
	for i in range(q):
		(v, w) = map(int, input().split())
		print(min(v, w))
else:
	for i in range(q):
		(v, w) = map(int, input().split())
		while v != w:
			if v > w:
				(v, w) = (w, v)
			w = (w + n - 2) // n
		print(v)


def main():
	(n, m) = map(int, input().split())
	ab = [list(map(int, input().split())) for _ in [0] * m]
	if n == 1:
		for (a, b) in ab:
			print(min(a, b))
		return
	for (a, b) in ab:
		while a != b:
			if a < b:
				b = (b + n - 2) // n
			else:
				a = (a + n - 2) // n
		print(a)
main()


(n, q, *t) = map(int, open(0).read().split())
for (v, w) in zip(t[::2], t[1::2]):
	if n - 1:
		while v != w:
			if v > w:
				(v, w) = (w, v)
			w = (w + n - 2) // n
	print(v)


(N, Q) = map(int, input().split())
if N > 1:

	def find_par(x):
		u = x % N - 1
		if u <= 0:
			u += N
		return (x - u - 1) // N + 1

	def path(x):
		s_node = x
		d = [s_node]
		while s_node != 1:
			s_node = find_par(s_node)
			d.append(s_node)
		return d
	for _ in range(Q):
		(v, w) = map(int, input().split())
		data1 = set(path(v))
		data2 = set(path(w))
		print(max(data1 & data2))
else:
	for _ in range(Q):
		(v, w) = map(int, input().split())
		print(min(v, w))


from bisect import *
from sys import stdin, stdout
readline = stdin.readline
(N, Q) = map(int, readline().split())
ans = []
if N == 1:
	for q in range(Q):
		(v, w) = map(int, readline().split())
		ans.append(str(v))
else:
	c = 1
	B = [1]
	while c < 10 ** 9:
		B.append(c + 1)
		c = c * N + 1
	for q in range(Q):
		(v, w) = map(int, readline().split())
		lv = bisect(B, v)
		lw = bisect(B, w)
		if lv < lw:
			w = (w + (B[lw - lv] - 1) * (N - 2)) // N ** (lw - lv)
		while v != w:
			v = (v + (N - 2)) // N
			w = (w + (N - 2)) // N
		ans.append(str(v))
stdout.write('\n'.join(ans))
stdout.write('\n')


import math
(N, Q) = map(int, input().split())
queries = []
for i in range(Q):
	(v, w) = map(int, input().split())
	queries.append([v, w])
if N == 1:
	for (v, w) in queries:
		print(min(v, w))
else:
	for (v, w) in queries:
		if 1 in [v, w]:
			print(1)
		else:
			(v, w) = (min(v, w), max(v, w))
			v -= 2
			w -= 2
			v_parents = [v]
			isReported = False
			while v > 0:
				v_parents.append(v // N - 1)
				v = v // N - 1
			while w > 0:
				w = w // N - 1
				if w in v_parents:
					print(w + 2)
					isReported = True
					break
			if not isReported:
				print(1)


import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
VW = [tuple(map(int, input().split())) for i in range(Q)]
ans = []
if N == 1:
	for (v, w) in VW:
		ans.append(min(v, w))
else:
	for (v, w) in VW:
		while v != w:
			if v > w:
				(v, w) = (w, v)
			w = (w + N - 2) // N
		ans.append(v)
print(*ans, sep='\n')


import bisect
(n, q) = [int(v) for v in input().split()]
if n != 1:
	tree_list = [0] + [(n ** (i + 1) - 1) // (n - 1) for i in range(100) if (n ** (i + 1) - 1) // (n - 1) <= 10 ** 9]

def upward(a):
	d = bisect.bisect_left(tree_list, a) - 1
	outlist = []
	for i in range(d + 1):
		outlist.append(a)
		if i < d:
			a -= tree_list[d - i] + 1
			a //= n
			a += tree_list[d - i - 1] + 1
	return (d, outlist)

def lca(a, b):
	(da, a_list) = upward(a)
	(db, b_list) = upward(b)
	if da < db:
		(da, db) = (db, da)
		(a_list, b_list) = (b_list, a_list)
	s = da - db
	ans = None
	for i in range(db + 1):
		if a_list[s + i] == b_list[i]:
			ans = a_list[s + i]
			break
	return ans
for i in range(q):
	(v, w) = [int(v) for v in input().split()]
	if n != 1:
		print(lca(v, w))
	else:
		print(min(v, w))


(N, Q) = map(int, input().split())
if N == 1:
	for i in range(Q):
		(V, W) = map(int, input().split())
		print(min(V, W))
else:
	p = []
	p.append(1)
	for i in range(40):
		p.append(p[-1] * N)
	for i in range(Q):
		(V, W) = map(int, input().split())
		v = []
		w = []
		dv = 0
		dw = 0
		while V > (p[dv + 1] - 1) // (N - 1):
			dv = dv + 1
		while W > (p[dw + 1] - 1) // (N - 1):
			dw = dw + 1
		v.append(V)
		e = V
		for j in range(dv, 0, -1):
			e = (e - (p[j] - 1) // (N - 1) - 1) // N + (p[j - 1] - 1) // (N - 1) + 1
			v.append(e)
		v.reverse()
		w.append(W)
		e = W
		for j in range(dw, 0, -1):
			e = (e - (p[j] - 1) // (N - 1) - 1) // N + (p[j - 1] - 1) // (N - 1) + 1
			w.append(e)
		w.reverse()
		ans = 1
		j = 0
		while j < len(v) and j < len(w) and (v[j] == w[j]):
			ans = v[j]
			j = j + 1
		print(ans)


(N, Q) = map(int, input().split())
if N == 1:
	for _ in range(Q):
		(v, w) = map(int, input().split())
		print(min(v, w))
else:
	L = [1]
	aa = 1

	def ch(k):
		return (k - 2) // N + 1

	def chh(a, b):
		if a == b:
			return a
		if a > b:
			(a, b) = (b, a)
		return chh(a, ch(b))
	for _ in range(Q):
		(v, w) = map(int, input().split())
		print(chh(v, w))


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
INF = float('inf')

def LI():
	return list(map(int, sys.stdin.readline().split()))

def I():
	return int(sys.stdin.readline())

def LIM():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def S():
	return sys.stdin.readline().strip()

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def LIRM(n):
	return [LIM() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]
mod = 1000000007
(n, q) = LI()
for (i, j) in LIR(q):
	if n == 1:
		print(min(i, j))
	else:
		while i != j:
			if i < j:
				(i, j) = (j, i)
			i = (i - 2) // n + 1
		print(i)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
for i in range(q):
	(u, v) = map(int, input().split())
	if n == 1:
		print(min(u, v))
		continue
	u -= 1
	v -= 1
	while u != v:
		if u > v:
			if (u - 1) // n > v:
				u = ((u - 1) // n - 1) // n
			else:
				u = (u - 1) // n
		elif (v - 1) // n > v:
			v = ((v - 1) // n - 1) // n
		else:
			v = (v - 1) // n
	print(u + 1)


from bisect import *
(N, Q) = map(int, input().split())
ans = []
if N == 1:
	for q in range(Q):
		(v, w) = map(int, input().split())
		print(v)
else:
	c = 1
	B = [1]
	while c < 10 ** 9:
		B.append(c + 1)
		c = c * N + 1
	for q in range(Q):
		(v, w) = map(int, input().split())
		for i in range(bisect(B, v), bisect(B, w)):
			w = (w + (N - 2)) // N
		while v != w:
			v = (v + (N - 2)) // N
			w = (w + (N - 2)) // N
		print(v)


import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
(N, Q) = map(int, input().split())
if N == 1:
	ans = [min(map(int, input().split())) for _ in range(Q)]
	print(*ans, sep='\n')
	exit()
ans = [-1] * Q
for i in range(Q):
	(x, y) = map(int, input().split())
	x_memo = [x]
	y_memo = [y]
	while x:
		x = (x + N - 2) // N
		x_memo.append(x)
	while y:
		y = (y + N - 2) // N
		y_memo.append(y)
	res = -1
	while x_memo and y_memo:
		xi = x_memo.pop()
		yi = y_memo.pop()
		if xi == yi:
			res = xi
		else:
			break
	ans[i] = res
print(*ans, sep='\n')


import sys
(N, Q) = map(int, input().split())
query = []
for i in range(Q):
	(v, w) = map(int, input().split())
	if v < w:
		(v, w) = (w, v)
	query.append((v - 1, w - 1))

def f(v, w):
	L = set()
	L.add(0)
	while w != 0:
		L.add(w)
		w = (w - 1) // N
	while v != 0:
		if v in L:
			return v + 1
		v = (v - 1) // N
	return 1
if N == 1:
	for (v, w) in query:
		print(w + 1)
	sys.exit()
for (v, w) in query:
	print(f(v, w))


import sys
readline = sys.stdin.readline
(N, Q) = map(int, readline().split())
for i in range(Q):
	(v, w) = map(int, readline().split())
	if N == 1:
		print(min(v, w))
		continue
	v -= 1
	w -= 1
	while v != w:
		if v > w:
			v = (v - 1) // N
		else:
			w = (w - 1) // N
	print(v + 1)