Let f be a [permutation] of length N, where N is even. The *riffle* of f is defined to be the permutation
g = (f(1), f(3), \ldots, f(N-1), f(2), f(4), \ldots, f(N))

You are given two integers N and K. Output the resultant permutation when you riffle the identity permutation of length N, K times.

The identity permutation of length N is {\sigma}_N = (1, 2, \ldots, N)

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of a single line of input, containing two space-separated integers N and K.

------ Output Format ------ 

For each test case, output the answer permutation as N space-separated integers in a new line.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 3 \cdot 10^{5}$
$1 ≤ K ≤ 10^{9}$
$N$ is even
- The sum of $N$ across test cases does not exceed $3 \cdot 10^{5}$

------ subtasks ------ 

Subtask 1 (30 points): $N$ is a power of $2$
Subtask 2 (70 points): Original constraints

----- Sample Input 1 ------ 
3
6 1
8 2
14 452
----- Sample Output 1 ------ 
1 3 5 2 4 6
1 5 2 6 3 7 4 8
1 10 6 2 11 7 3 12 8 4 13 9 5 14
----- explanation 1 ------ 
Test case $1$: Performing the riffle on $\sigma_{6} = (1, 2, 3, 4, 5, 6)$ once results in $(1, 3, 5, 2, 4, 6)$, by definition.

Test case $2$: The process goes as follows:
- Performing the riffle on $(1, 2, 3, 4, 5, 6, 7, 8)$ results in $(1, 3, 5, 7, 2, 4, 6, 8)$
- Performing the riffle on $(1, 3, 5, 7, 2, 4, 6, 8)$ results in $(1, 5, 2, 6, 3, 7, 4, 8)$

Difficulty: VERY_HARD

Starter code:

Solutions:
from collections import deque
import math

def applyPermutation(seq, permutation):
	newSeq = []
	for i in range(len(seq)):
		newSeq.append(seq[permutation[i]])
	return newSeq

def permute(seq, permutation, b):
	while b > 0:
		if b & 1:
			seq = applyPermutation(seq, permutation)
		permutation = applyPermutation(permutation, permutation)
		b >>= 1
	return seq

def find_length(graph, n):
	lis = []
	vis = [False] * n
	for i in range(n):
		length = 0
		if not vis[i]:
			q = deque([i])
			vis[i] = True
			while q:
				node = q.popleft()
				length += 1
				for j in graph[node]:
					if not vis[j]:
						q.append(j)
						vis[j] = True
			lis.append(length)
	return lis

def LCMofArray(a):
	lcm = a[0]
	for i in range(1, len(a)):
		lcm = lcm * a[i] // math.gcd(lcm, a[i])
	return lcm
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	seq = list(range(1, n + 1))
	seq = [i - 1 for i in seq]
	permutation = list(range(1, n, 2)) + list(range(2, n + 1, 2))
	permutation = [i - 1 for i in permutation]
	graph = []
	for i in range(n):
		graph.append([])
	for i in range(n):
		u = permutation[i]
		v = seq[i]
		graph[u].append(v)
	len_arr = find_length(graph, n)
	lcm = LCMofArray(len_arr)
	k = k % lcm
	res = permute(seq, permutation, k)
	res = [i + 1 for i in res]
	print(*res)


def applyPermutation(seq, permutation):
	newSeq = []
	for i in range(len(seq)):
		newSeq.append(seq[permutation[i]])
	return newSeq

def permute(seq, permutation, b):
	while b > 0:
		if b & 1:
			seq = applyPermutation(seq, permutation)
		permutation = applyPermutation(permutation, permutation)
		b >>= 1
	return seq
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	seq = list(range(1, n + 1))
	seq = [i - 1 for i in seq]
	permutation = list(range(1, n, 2)) + list(range(2, n + 1, 2))
	permutation = [i - 1 for i in permutation]
	res = permute(seq, permutation, k)
	res = [i + 1 for i in res]
	print(*res)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	sequence = [i for i in range(1, n + 1)]
	permutation = [2 * i + 1 for i in range(n // 2)]
	sub_perm = [2 * i for i in range(1, n // 2 + 1)]
	permutation.extend(sub_perm)

	def apply_perm(seq, perm):
		new_seq = seq.copy()
		for i in range(len(seq)):
			new_seq[i] = seq[perm[i] - 1]
		return new_seq

	def perm_k(seq, perm, k):
		while k:
			if k % 2:
				seq = apply_perm(seq, perm)
			perm = apply_perm(perm, perm)
			k >>= 1
		return seq
	print(*perm_k(sequence, permutation, k))


def exp_permutation(seq, p, n):

	def permute(_seq, permutation):
		return [_seq[i] for i in permutation]
	while n:
		if n % 2:
			seq = permute(seq, p)
		p = permute(p, p)
		n = n // 2
	return seq
t = int(input())
while t:
	(N, K) = map(int, input().split())
	seq = list(range(1, N + 1))
	p = [i - 1 for i in range(1, N, 2)] + [i - 1 for i in range(2, N + 1, 2)]
	for k in exp_permutation(seq, p, K):
		print(k, end=' ')
	print()
	t = t - 1


def binexpo(a, b, m):
	a %= m
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b >>= 1
	return res

def exe():
	(n, k) = map(int, input().split())
	l = []
	for i in range(1, n + 1):
		l.append(i)
	kk = binexpo(2, k, n - 1)
	p = kk - 1 % (n - 1)
	if kk - 1 < 0:
		p += n - 1
	print(1, end=' ')
	m = 1
	for i in range(n - 2):
		print(l[(m + p) % (n - 1)], end=' ')
		m = l[(m + p) % (n - 1)]
	print(n)
	return
for i in range(int(input())):
	exe()


t = int(input())

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	lcm = x * y // gcd(x, y)
	return lcm

def riffle(permutations, n, k):
	positions = []
	for i in range(n):
		positions.append(i + 1)
	for permutation in permutations:
		for i in range(len(permutation)):
			positions[permutation[(i + k) % len(permutation)]] = permutation[i] + 1
	return positions

def backwardsRiffe(positions, n):
	newPositions = []
	positionsFirstHalf = positions[0:n // 2]
	positionsSecondHalf = positions[n // 2:]
	for i in range(n // 2):
		newPositions.append(positionsFirstHalf[i])
		newPositions.append(positionsSecondHalf[i])
	return newPositions

def singleRiffle(currentPositions, n):
	if currentPositions % 2:
		return n // 2 + (currentPositions - 1) // 2
	else:
		return currentPositions // 2

def findOrder(permutations):
	if len(permutations) == 0:
		return 1
	order = len(permutations[0])
	for permutation in permutations:
		order = lcm(order, len(permutation))
	return order

def findPermutations(n):
	permutations = []
	positionsNotSeen = set()
	for i in range(1, n - 1):
		positionsNotSeen.add(i)
	count = 0
	while count != n - 2:
		permutation = []
		startingPosition = positionsNotSeen.pop()
		currentPosition = startingPosition
		currentPosition = singleRiffle(currentPosition, n)
		permutation.append(currentPosition)
		count += 1
		while startingPosition != currentPosition:
			positionsNotSeen.remove(currentPosition)
			currentPosition = singleRiffle(currentPosition, n)
			permutation.append(currentPosition)
			count += 1
		permutations.append(permutation)
	return permutations
for _ in range(t):
	inputs = [int(item) for item in input().split()]
	n = inputs[0]
	k = inputs[1]
	permutations = findPermutations(n)
	order = findOrder(permutations)
	riffleAmount = k % order
	print(*riffle(permutations, n, k))


def build_perm(n):
	p = []
	p = list(range(0, n, 2)) + list(range(1, n + 1, 2))
	return p

def permutate(sequence, perm_list):
	new_sequence = [-1] * len(sequence)
	for (i, j) in enumerate(perm_list):
		new_sequence[i] = sequence[j]
	return new_sequence

def multiple_permutation(sequence, permutation, k):
	while k > 0:
		if k & 1:
			sequence = permutate(sequence, permutation)
		permutation = permutate(permutation, permutation)
		k = k // 2
	return sequence
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	permutation = build_perm(n)
	sequence = list(range(1, n + 1))
	print(*multiple_permutation(sequence, permutation, k))


def Permutation(a, b):
	ans = [0] * len(a)
	for i in range(len(a)):
		ans[i] = a[b[i]]
	return ans

def PowerPermutation(a, b, c):
	while c:
		if c & 1:
			a = Permutation(a, b)
		b = Permutation(b, b)
		c >>= 1
	return a
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = [i for i in range(1, N + 1)]
	Perm = [i for i in range(0, N, 2)] + [i for i in range(1, N, 2)]
	print(*PowerPermutation(A, Perm, K))


def Permutation(a, perm):
	new_seq = [0] * len(a)
	for i in range(len(a)):
		new_seq[i] = a[perm[i]]
	return new_seq

def PowerPermutation(a, b, c):
	while c:
		if c & 1:
			a = Permutation(a, b)
		b = Permutation(b, b)
		c >>= 1
	return a
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = [i for i in range(1, N + 1)]
	perm = []
	for i in range(0, N, 2):
		perm.append(i)
	for i in range(1, N, 2):
		perm.append(i)
	print(*PowerPermutation(A, perm, K))


def solve(n, k):
	next = [0] * (n + 1)
	ans = [False] * (n + 1)
	for i in range(1, len(next)):
		if i & 1:
			next[1 + i // 2] = i
		else:
			next[n // 2 + i // 2] = i
	for i in range(1, len(next)):
		if not ans[i]:
			ans[i] = True
			curr = i
			cycle = []
			cycle.append(curr)
			while next[curr] != i:
				curr = next[curr]
				cycle.append(curr)
				ans[i] = True
			for j in range(0, len(cycle)):
				ans[cycle[j]] = cycle[(j + k) % len(cycle)]
	for i in range(1, len(ans)):
		print(ans[i], end=' ')
	print()
t = int(input())
while t:
	line = input().split(' ')
	n = int(line[0])
	k = int(line[1])
	solve(n, k)
	t -= 1


t = int(input())
while t:
	(a, b) = map(int, input().split(' '))
	a = a - 1
	for i in range(a + 1):
		if (2 << i) % a == 1:
			ct = i + 1
			break
	if ct == b:
		itr = a + 1
	elif ct > b:
		itr = (1 << b) % a
	elif ct < b:
		itr = 1 << b % ct % a
	z = 0
	for i in range(a + 1):
		print(z + 1, end=' ')
		z = (z + itr) % a
		if z == 0:
			z = a
	print()
	t -= 1


tcases = int(input())
while tcases:
	(n, k) = map(int, input().split(' '))
	n = n - 1
	for i in range(n + 1):
		if (2 << i) % n == 1:
			ct = i + 1
			break
	if ct == k:
		itr = n + 1
	elif ct > k:
		itr = (1 << k) % n
	elif ct < k:
		itr = 1 << k % ct % n
	z = 0
	for i in range(n + 1):
		print(z + 1, end=' ')
		z = (z + itr) % n
		if z == 0:
			z = n
	print()
	tcases -= 1


def mul(a, b, n):
	tmp = {}
	for i in range(n):
		tmp[i + 1] = a[b[i + 1]]
	return tmp
t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split()]
	positions = {}
	for i in range(1, n // 2 + 1):
		positions[i] = 2 * i - 1
	for i in range(n // 2 + 1, n + 1):
		positions[i] = 2 * (i - n // 2)
	inipositions = {}
	for i in range(n):
		inipositions[i + 1] = i + 1
	while k:
		if k & 1:
			inipositions = mul(inipositions, positions, n)
		positions = mul(positions, positions, n)
		k //= 2
	print(' '.join(map(str, list(inipositions.values()))))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	n -= 1
	for j in range(n + 1):
		if (2 << j) % n == 1:
			c = j + 1
			break
	if c == k:
		r = n + 1
	elif c > k:
		r = (1 << k) % n
	elif c < k:
		r = 1 << k % c % n
	z = 0
	for y in range(n + 1):
		print(z + 1, end=' ')
		z = (z + r) % n
		if z == 0:
			z = n
	print()


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	vis = set()
	ans = [i + 1 for i in range(n)]
	for i in range(2, n):
		if i not in vis:
			vis.add(i)
			temp = [i]
			start = i
			while True:
				start *= 2
				start -= 1
				start %= n - 1
				if start == temp[0] or not start:
					break
				temp.append(start)
				vis.add(start)
			l = len(temp)
			for j in range(l):
				ans[temp[j] - 1] = temp[(j + k) % l]
	print(*ans)


T = int(input())
while T:
	(N, K) = map(int, input().split(' '))
	N = N - 1
	for i in range(N + 1):
		if (2 << i) % N == 1:
			temp = i + 1
			break
	if temp == K:
		itr = N + 1
	elif temp > K:
		itr = (1 << K) % N
	elif temp < K:
		itr = 1 << K % temp % N
	Z = 0
	for i in range(N + 1):
		print(Z + 1, end=' ')
		Z = (Z + itr) % N
		if Z == 0:
			Z = N
	print()
	T -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 2:
		print(1, 2)
		continue
	x = [0]
	for i in range(1, n + 1):
		if i % 2 == 1:
			x.append((i + 1) // 2)
		else:
			x.append((n + i) // 2)
	flag = [0] * (n - 2)
	i = 2
	chain = []
	ct = 0
	while ct < n - 2:
		tmp = []
		while 1:
			if flag[x[i] - 2]:
				break
			ct += 1
			tmp.append(x[i])
			flag[x[i] - 2] = 1
			i = x[i]
		if len(tmp) > 0:
			chain.append(tmp)
		i += 1
	ans = [0] * n
	ans[0] = 1
	for i in range(len(chain)):
		m = k % len(chain[i])
		for j in range(len(chain[i])):
			ans[chain[i][(m + j) % len(chain[i])] - 1] = chain[i][j]
	ans[-1] = n
	for i in ans:
		print(i, end=' ')
	print('')