Alice initially has a string S of length N, and she decides to modify it! Her modification consists of K steps numbered from 1 to K. In the i-th step, Alice reverses the prefix of length i of S.

For example, suppose Alice starts with S = \texttt{abferty}, and she modifies it via 3 steps, then:
After the first step, \textcolor{blue}{\texttt{a}}\texttt{bferty} \rightarrow S = \texttt{abferty}
After the second step, \textcolor{blue}{\texttt{ab}}\texttt{ferty} \rightarrow S = \texttt{baferty}
After the third step, \textcolor{blue}{\texttt{baf}}\texttt{erty} \rightarrow S = \texttt{faberty}
So after 3 steps, her string becomes S = \texttt{faberty}.

After performing her K-step modification, Alice ends up with the string S'. Now she challenges you to find the original string S. Can you do it?

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

- The first line of the input contains a single integer T - the number of test cases. The test cases then follow.
- The first line of the test case contains two space-separated integers N and K - the length of the string and the number of steps in Alice's modification.
- The second line of the test case contains S' - the final string obtained after the modification.

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

For each test case, output the original string S.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{6}$
$1 ≤ K ≤ N$
$|S'| = N$
$S'$ contains only lowercase alphabets
- Sum of $N$ overall cases does not exceed $10^{6}$.

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

Subtask $1$ (30 points): $1 ≤ N \cdot K ≤ 2000$
Subtask $2$ (70 points): Original constraints

----- Sample Input 1 ------ 
3
7 3
faberty
7 5
bbaaaba
4 4
zxwy

----- Sample Output 1 ------ 
abferty
aababba
wxyz

----- explanation 1 ------ 
- Test case $2$: The modification steps from $S$ to $S'$ is as follow:
- $1$-st step: $\textcolor{blue}{\texttt{a}}\texttt{ababba} \rightarrow S = \texttt{aababba}$
- $2$-nd step: $\textcolor{blue}{\texttt{aa}}\texttt{babba} \rightarrow S = \texttt{aababba}$
- $3$-rd step: $\textcolor{blue}{\texttt{aab}}\texttt{abba} \rightarrow S = \texttt{baaabba}$
- $4$-th step: $\textcolor{blue}{\texttt{baaa}}\texttt{bba} \rightarrow S = \texttt{aaabbba}$
- $5$-th step: $\textcolor{blue}{\texttt{aaabb}}\texttt{ba} \rightarrow S = \texttt{bbaaaba}$
- Test case $3$: The modification steps from $S$ to $S'$ is as follow:
- $1$-st step: $\textcolor{blue}{\texttt{w}}\texttt{xyz} \rightarrow S = \texttt{wxyz}$
- $2$-nd step: $\textcolor{blue}{\texttt{wx}}\texttt{yz} \rightarrow S = \texttt{xwyz}$
- $3$-rd step: $\textcolor{blue}{\texttt{xwy}}\texttt{z} \rightarrow S = \texttt{ywxz}$
- $4$-th step: $\textcolor{blue}{\texttt{ywxz}} \rightarrow S = \texttt{zxwy}$

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

String algorithms

Amortized analysis

Data structures

Ad-hoc
Skill types: Data structures

Amortized analysis

Starter code:

Solutions:
def soln(n, k, s):
	beg = 0
	end = k - 1
	res = [''] * n
	for i in range(k):
		if not i & 1:
			res[i] = s[beg]
			beg += 1
		else:
			res[i] = s[end]
			end -= 1
	res[:k] = res[k - 1::-1]
	for i in range(k, n):
		res[i] = s[i]
	return ''.join(res)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	print(soln(n, k, s))


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	str1 = input()
	str2 = str1[k:]
	emp = ''
	i = 0
	j = k - 1
	while i < j:
		emp += str1[i]
		emp += str1[j]
		i += 1
		j -= 1
	if i == j:
		emp += str1[j]
	k1 = emp[::-1]
	print(k1 + str2)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	srt = input()
	kstr = srt[:k]
	lst_str = srt[k:]
	oprn_lst = [' '] * (n + 1)
	odd = False
	if k % 2 == 1:
		odd = True
	nm = k // 2
	k -= 1
	cnt = 0
	fin_ind = 0
	for i in range(nm):
		oprn_lst[n - cnt] = kstr[i]
		oprn_lst[n - cnt - 1] = kstr[k - i]
		cnt += 2
		fin_ind += 1
	if odd:
		oprn_lst[0] = kstr[fin_ind]
	print(''.join(oprn_lst).replace(' ', '') + lst_str)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	x = s[:k]
	y = s[k:]
	r = ''
	for i in range(len(x) // 2):
		r += x[i]
		r += x[-(i + 1)]
	if len(x) % 2:
		r += x[len(x) // 2]
	r = r[::-1]
	print(r + y)


import sys
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(e, res) = (s[k:], s[:k])
	arr = ['' for i in range(k)]
	cnt = 0
	for i in range(k - 1, -1, -2):
		arr[i] = s[cnt]
		cnt += 1
	for i in range(k):
		if arr[i] == '':
			arr[i] = s[cnt]
			cnt += 1
	for i in arr:
		print(i, end='')
	print(e)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l1 = k
	s2 = s[k:]
	s1 = s[:k]
	s3 = ''
	l1 -= 1
	l2 = 0
	while l1 >= l2:
		s3 += s1[l2]
		if l1 != l2:
			s3 += s1[l1]
		l1 -= 1
		l2 += 1
	print(s3[::-1] + s2)


for _ in range(int(input())):
	(n, r) = map(int, input().split(' '))
	s = input()
	res = ''
	(prev_s, last_res) = (s[:r], s[r:])
	(p1, p2) = (0, r - 1)
	while p1 <= p2:
		res += prev_s[p1]
		if p1 != p2:
			res += prev_s[p2]
		p1 += 1
		p2 -= 1
	print(res[::-1] + last_res)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	ext = s[k:]
	solve = s[:k]
	l = ['' for i in range(k)]
	c = 0
	for i in range(k - 1, -1, -2):
		l[i] = s[c]
		c += 1
	for i in range(k):
		if l[i] == '':
			l[i] = s[c]
			c += 1
	for i in l:
		print(i, end='')
	print(ext)


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	s = input()
	lst = s[b:]
	s = s[:b]
	r = ''
	for i in range(len(s) // 2):
		r += s[i]
		r += s[-(i + 1)]
	if len(s) % 2:
		r += s[len(s) // 2]
	r = r[::-1]
	print(r + lst)


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	s = list(input())
	ans = ''
	s1 = r // 2
	s2 = r // 2 - 1
	if r % 2 == 1:
		print(s[s1], end='')
		s1 += 1
	for i in range(r // 2):
		print(s[s1], end='')
		print(s[s2], end='')
		s2 -= 1
		s1 += 1
	print(ans, end='')
	print(''.join(s[r:]))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	i = 0
	j = k - 1
	res = ''
	while i < j:
		res += s[i]
		res += s[j]
		i += 1
		j -= 1
	if i == j:
		res = res + s[i]
	m = res[::-1]
	o = s[k:]
	print(m + o)


from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]

def rev_st(st, k):
	ans = ''
	i = 0
	j = k - 1
	f = True
	while i <= j:
		if f:
			ans = ans + st[i]
			i += 1
		else:
			ans = ans + st[j]
			j -= 1
		f = not f
	ans = ans[::-1]
	for e in range(k, len(st)):
		ans = ans + st[e]
	print(ans)
for _ in range(ii()):
	(n, k) = il()
	st = ip()
	rev_st(st, k)


def integer_list():
	return list(map(int, input().split()))

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())
import math
import sys
from collections import Counter

def main():
	(i, j) = (0, k - 1)
	ans = ''
	flag = True
	while i <= j:
		if flag:
			ans = s[i] + ans
			flag = False
			i += 1
		else:
			ans = s[j] + ans
			flag = True
			j -= 1
	print(ans + s[k:])
t = int(input())
for _ in range(t):
	(n, k) = integer_list()
	s = input()
	main()


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	str = input()
	ans = ''
	s = 0
	e = k - 1
	while s < e:
		ans += str[s]
		ans += str[e]
		s += 1
		e -= 1
	if s == e:
		ans += str[s]
	print(ans[::-1] + str[k:])


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	st = input()
	par = +1
	if d % 2 == 1:
		par = -1
	s = ''
	j = d // 2
	for i in range(d):
		j += par * i
		s += st[j]
		par = -par
	try:
		print(s + st[d:])
	except:
		print(s)


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	s = input()
	mainarr = list(s)
	arr = []
	arr[:] = mainarr[:n]
	newarr = []
	(l, r) = (0, n - 1)
	for i in range(0, n):
		if i % 2 == 0:
			newarr.append(arr[l])
			l += 1
		else:
			newarr.append(arr[r])
			r -= 1
	newarr = newarr[::-1]
	ans = newarr + mainarr[n:]
	print(''.join(ans))


t = int(input())
while t:
	p = input().split()
	s = input()
	d = int(p[1])
	lenn = int(p[1])
	x = ''
	x += s[d // 2]
	if lenn % 2 == 1:
		i = 1
		while i <= d // 2:
			x += s[d // 2 + i]
			x += s[d // 2 - i]
			i += 1
		print(x + s[d:])
	else:
		i = 1
		while i < d // 2:
			x += s[d // 2 - i]
			x += s[d // 2 + i]
			i += 1
		print(x + s[0] + s[d:])
	t -= 1


def inpNum():
	return int(input())

def inpNums():
	return tuple(list(map(int, input().split())))

def inpList():
	return list(map(int, input().split()))

def solve(t: int):
	(N, K) = inpNums()
	s = input()
	ans = ''
	dir = 1 if K % 2 == 0 else -1
	step = 0
	i = int(K / 2)
	while K:
		idx = i + step * dir
		dir *= -1
		step += 1
		K -= 1
		i = idx
		ans = ans + s[idx]
	for i in range(len(ans), N):
		ans = ans + s[i]
	print(ans)
for t in range(int(input())):
	solve(t)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	x = s[k:]
	r = ''
	i = 0
	j = k - 1
	while i < j:
		r = r + s[i]
		r = r + s[j]
		i = i + 1
		j = j - 1
	if i == j:
		r = r + s[i]
	a = r[::-1] + x
	print(a)


def solve(s, k):
	res = ['-'] * len(s)
	res[-len(s) + k:] = s[-len(s) + k:]
	is_left = True
	i = -len(s) + k - 1
	(left, right) = (0, k - 1)
	while left <= right:
		if is_left:
			res[i] = s[left]
			left += 1
		else:
			res[i] = s[right]
			right -= 1
		i -= 1
		is_left = not is_left
	return ''.join(res)

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		s = input()
		result = solve(s, k)
		print(result)
main()


t = int(input())
while t:
	(n, k) = map(int, input().split())
	s = input()
	a = s[0:k]
	b = s[k:]
	c = []
	var1 = 0
	var2 = k - 1
	for i in range(k):
		if i % 2 == 0:
			c.append(a[var1])
			var1 = var1 + 1
		else:
			c.append(a[var2])
			var2 = var2 - 1
	d = c[::-1]
	e = ''.join(d)
	res = e + b
	print(res)
	t = t - 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	inp = input()
	pref = ''
	i = 0
	l = 0
	while l <= k:
		if i != k - i - 1:
			pref += f'{inp[i]}{inp[k - i - 1]}'
			l += 2
			i += 1
		else:
			pref += inp[i]
			break
		if l == k:
			break
	print(pref[::-1] + inp[k:])


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	S = input()
	p1 = S[:k]
	p2 = S[k:n]
	p11 = p1[:k // 2]
	p11 = p11[::-1]
	p12 = p1[k // 2:]
	ans = ''
	if k % 2 == 0:
		for i in range(k // 2):
			ans = ans + p12[i] + p11[i]
	else:
		ans = ans + p12[0]
		for i in range(1, k // 2 + 1):
			ans = ans + p12[i] + p11[i - 1]
	print(ans + p2)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	ans = list(s)
	ans[k - 1::-2] = s[0:(k + 1) // 2]
	ans[k % 2:k:2] = s[(k + 1) // 2:k]
	print(''.join(ans))


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	l = input()
	left = []
	right = []
	r = [None] * M
	if M % 2 == 0:
		right = l[M // 2:M]
		left = l[M // 2 - 1::-1]
		r[::2] = right
		r[1::2] = left
		r[M:] = l[M:]
	else:
		right = l[M // 2 + 1:M]
		left = l[M // 2::-1]
		r[1::2] = right
		r[::2] = left
		r[M:] = l[M:]
	print(*r, sep='')


try:
	t = int(input())
	while t:
		(n, k) = map(int, input().split())
		s = input()
		org = ''
		(i, j) = (0, k - 1)
		while i < j:
			org += s[i]
			org += s[j]
			i += 1
			j -= 1
		if i == j:
			org += s[i]
		org = org[::-1] + s[k:n]
		print(org)
		t -= 1
except EOFError as e:
	pass


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	ans = ''
	left = 0
	right = k - 1
	while left < right:
		ans += s[left]
		ans += s[right]
		left += 1
		right -= 1
	if left == right:
		ans += s[left]
	print(ans[::-1] + s[k:])


test_cases = int(input())
for _ in range(test_cases):
	(N, K) = map(int, input().split())
	S = input().rstrip('\n')
	S1 = list(S)
	Current_Character = 0
	for i in range(K, 0, -2):
		S1[i - 1] = S[Current_Character]
		Current_Character += 1
	Next = 1 + K % 2
	for i in range(Next, K, 2):
		S1[i - 1] = S[Current_Character]
		Current_Character += 1
	print(''.join(S1))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = [0] * n
	s = input()
	c = 0
	if k % 2 == 0:
		for j in range(k - 1, 0, -2):
			l[j] = s[c]
			c += 1
		for x in range(n):
			if l[x] == 0:
				l[x] = s[c]
				c += 1
		ans = ''
		for y in l:
			ans += y
		print(ans)
	else:
		for z in range(k - 1, -1, -2):
			l[z] = s[c]
			c += 1
		for w in range(n):
			if l[w] == 0:
				l[w] = s[c]
				c += 1
		ans = ''
		for q in l:
			ans += q
		print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = []
	for i in range(n):
		l.append(0)
	s = input()
	j = 0
	if k % 2 == 0:
		for i in range(k - 1, 0, -2):
			l[i] = s[j]
			j += 1
		for i in range(n):
			if l[i] == 0:
				l[i] = s[j]
				j += 1
		ans = ''
		for i in l:
			ans += i
		print(ans)
	else:
		for i in range(k - 1, -1, -2):
			l[i] = s[j]
			j += 1
		for i in range(n):
			if l[i] == 0:
				l[i] = s[j]
				j += 1
		ans = ''
		for i in l:
			ans += i
		print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s1 = input()
	s = list(s1)
	x = 0
	for i in range(k - 1, -1, -2):
		s[i] = s1[x]
		x += 1
	for j in range((i + 1) % 2, k - 1, 2):
		s[j] = s1[x]
		x += 1
	print(''.join(s))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	indlist = []
	if k % 2 == 0:
		count = k
		x = 0
		for i in range(k):
			indlist.append(count)
			if count - 2 == 0:
				x = 1
				count = -1
			if x == 0:
				count -= 2
			else:
				count += 2
	else:
		count = k
		x = 0
		for i in range(k):
			indlist.append(count)
			if count == 1:
				x = 1
				count = 0
			if x == 0:
				count -= 2
			else:
				count += 2
	sliced = s[0:k]
	for i in range(len(indlist)):
		s[indlist[i] - 1] = sliced[i]
	for i in s:
		print(i, end='')
	print()


ans = ''
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	sub1 = ''
	sub2 = s[k:]
	(l, r) = (0, k - 1)
	while l <= r:
		sub1 += s[l]
		if l != r:
			sub1 += s[r]
		r -= 1
		l += 1
	ans += sub1[::-1] + sub2 + '\n'
print(ans)


from operator import sub
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	s = list(input())
	ss = []
	(l, r) = (0, k - 1)
	for i in range(k):
		if i % 2 == 0:
			ss.append(s[l])
			l += 1
		else:
			ss.append(s[r])
			r -= 1
	s = list(reversed(ss)) + s[k:]
	print(''.join(s))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	s2 = s[k:]
	low = 0
	hi = k - 1
	ans = ''
	while low < hi:
		ans += s[low] + s[hi]
		low += 1
		hi -= 1
	if low == hi:
		ans += s[low]
	ans = ans[::-1]
	ans = ans + s2
	print(ans)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	med = math.ceil((k - 1) / 2)
	newStr = ''
	newStr += s[med]
	if k % 2 == 0:
		for i in range(1, med + 1):
			if med - i >= 0:
				newStr += s[med - i]
			if med + i <= k - 1:
				newStr += s[med + i]
	else:
		for i in range(1, med + 1):
			if med + i <= k - 1:
				newStr += s[med + i]
			if med - i >= 0:
				newStr += s[med - i]
	newStr += s[k:]
	print(newStr)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	mid = k // 2
	if k % 2 == 1:
		(ans, i, j) = (s[mid], mid - 1, mid + 1)
		while i >= 0:
			ans += s[j]
			ans += s[i]
			i -= 1
			j += 1
	else:
		(ans, j, i) = ('', mid, mid - 1)
		while i >= 0:
			ans += s[j]
			ans += s[i]
			i -= 1
			j += 1
	for i in range(k, n):
		ans += s[i]
	print(ans)


from collections import Counter
from math import ceil, floor, log, gcd
import bisect as bs
import sys
input = sys.stdin.readline
inp_lis = lambda : list(map(int, input().split()))
inp_multi = lambda : map(int, input().split())
inp_int = lambda : int(input().strip())
for _ in range(int(input().strip())):
	(n, k) = inp_multi()
	s = input().strip()
	s2 = s[k:]
	m = k // 2
	if k % 2 != 0:
		m += 1
	l = [0] * k
	t = k
	if k % 2 == 0:
		t2 = 1
	else:
		t2 = 2
	for i in range(k):
		if i < m:
			l[t - i * 2 - 1] = s[i]
		else:
			l[t2 - 1] = s[i]
			t2 += 2
	ans = ''.join(l)
	print(ans + s2)


def check(n, k, s):
	sharma = s[0:k]
	data = s[k:]
	ans = ''
	for i in range(0, k // 2):
		ans = sharma[-(i + 1)] + sharma[i] + ans
	if k % 2 != 0:
		ans = sharma[k // 2:k // 2 + 1] + ans
	return ans + data
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(check(n, k, s))


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	S = input()
	res = ''
	i = 0
	j = K - 1
	while i < j:
		res = res + S[i]
		res = res + S[j]
		i = i + 1
		j = j - 1
	if i == j:
		res = res + S[i]
	res = res[::-1]
	tmp = res + S[K:N]
	print(tmp)


import sys

def reverse(answer, i):
	for j in range(i // 2):
		(answer[j], answer[i - j - 1]) = (answer[i - j - 1], answer[j])

def findOriginalString(N, K, string):
	answer = []
	answer.append(string[K // 2])
	if K % 2:
		x = 2
		flag = -1
		j = K // 2 + 1
		while j >= 0 and j < K:
			answer.append(string[j])
			if flag == -1:
				j -= x
				flag = 1
			else:
				j += x
				flag = -1
			x += 1
	else:
		x = 2
		flag = -1
		j = K // 2 - 1
		while j >= 0 and j < K:
			answer.append(string[j])
			if flag == -1:
				j += x
				flag = 1
			else:
				j -= x
				flag = -1
			x += 1
	for i in range(K, N):
		answer.append(string[i])
	return ''.join(answer)

def main():
	test_case = int(sys.stdin.readline())
	for tc in range(test_case):
		(N, K) = map(int, sys.stdin.readline().split())
		string = sys.stdin.readline().strip('\n')
		print(findOriginalString(N, K, string))
main()


n = int(input())
for i in range(n):
	(length, moves) = [int(x) for x in str(input()).split(' ')]
	word = str(input())
	a = ''
	b = word[moves:]
	c = word[:moves]
	is_odd = moves % 2 != 0
	for j in range(moves // 2):
		a = c[j] + a
		a = c[moves - 1 - j] + a
	if is_odd:
		a = c[moves // 2] + a
	print(a + b)


from math import ceil
for i in range(int(input())):
	(a, b) = map(int, input().split())
	x = input()
	other = x[b:]
	before = x[:b]
	ans = ''
	i = 0
	j = b - 1
	while i < j:
		ans += before[i] + before[j]
		i += 1
		j -= 1
	if i == j:
		ans += before[i]
	print(ans[::-1] + other)


import sys
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(input())
	a = ''
	p = int(k / 2)
	for i in range(k):
		if i % 2 == 0:
			if k % 2 == 0:
				p += i
			else:
				p -= i
		elif k % 2 == 0:
			p -= i
		else:
			p += i
		a += s[p]
	print(a + s[k:])


t = int(input())
for _ in range(t):
	n = input().split()
	s = input()
	d = int(n[1])
	le = int(n[1])
	x = ''
	x += s[d // 2]
	if le % 2 == 1:
		j = 1
		while j <= d // 2:
			x += s[d // 2 + j]
			x += s[d // 2 - j]
			j += 1
		print(x + s[d:])
	else:
		j = 1
		while j < d // 2:
			x += s[d // 2 - j]
			x += s[d // 2 + j]
			j += 1
		print(x + s[0] + s[d:])


for _ in range(int(input())):
	z = [int(i) for i in input().split()]
	b = z[1]
	st = input()
	st1 = st[b:]
	s = st[:b]
	out = ''
	for i in range(len(s) // 2):
		out += s[i]
		out += s[-(i + 1)]
	if len(s) % 2:
		out += s[len(s) // 2]
	out = out[::-1]
	print(out + st1)


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	ans = ''
	i = 0
	j = k - 1
	while i < j:
		ans += s[i]
		ans += s[j]
		i += 1
		j -= 1
	if i == j:
		ans += s[i]
	ans = ans[::-1]
	ans += s[k:]
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = k
	l = k
	x = ''
	x += s[d // 2]
	if l % 2 == 1:
		i = 1
		while i <= d // 2:
			x += s[d // 2 + i]
			x += s[d // 2 - i]
			i += 1
		print(x + s[d:])
	else:
		i = 1
		while i < d // 2:
			x += s[d // 2 - i]
			x += s[d // 2 + i]
			i += 1
		print(x + s[0] + s[d:])


ans = []
testcase = int(input())
for i in range(0, testcase):
	string = ''
	li = []
	flag = 0
	(lenght, key) = map(int, input().split())
	ss = list(input())
	for i in range(lenght):
		li.append([ss[i], i + 1])
	for i in range(lenght):
		if key == 0:
			key = 1
			flag = 1
		elif key == -1:
			key = 2
			flag = 1
		li[i][1] = key
		if flag == 0:
			key -= 2
		elif flag == 1:
			key += 2
	li.sort(key=lambda x: x[1])
	for ele in range(lenght):
		string = string + li[ele][0]
	ans.append(string)
for sol in ans:
	print(sol)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	t = ''
	i = 0
	p = k - 1
	while i < p:
		t = s[i] + t
		t = s[p] + t
		i += 1
		p -= 1
	if k % 2 != 0:
		t = s[i] + t
	print(t + s[k:])


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	x = ''
	c = k // 2
	i = 1
	if k % 2 == 0:
		while i <= k // 2:
			x += a[k // 2 + i - 1]
			x += a[k // 2 - i]
			i += 1
		print(x + a[k:])
	else:
		while i <= k // 2:
			x += a[k // 2 + i]
			x += a[k // 2 - i]
			i += 1
		print(a[k // 2] + x + a[k:])


for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	s1 = s[:k]
	s4 = s[k:]
	n_s = ''
	for i in range(len(s1) // 2):
		n_s += s1[i]
		n_s += s1[-(i + 1)]
	if len(s1) % 2:
		n_s += s1[len(s1) // 2]
	n_s = n_s[::-1]
	print(n_s + s4)


import sys
import math
import random

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

def in1():
	return int(input())
for _ in range(in1()):
	(n, k) = get_line()
	s = str(input())
	s1 = list(s)
	t = s[k:]
	t1 = ''
	if k % 2 == 0:
		for i in range(k // 2):
			t1 += s1[i]
			t1 += s1[k - i - 1]
		t5 = ''.join(t1[::-1])
	else:
		for i in range(k // 2 + 1):
			t1 += s1[i]
			t1 += s1[k - i - 1]
		t5 = ''.join(t1[::-1])
		t5 = t5[1:]
	t3 = t5 + t
	print(t3)


x = int(input())
for i in range(x):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = input()
	if k & 1 == 0:
		z = k // 2
		b = 1
		while z < k:
			print(a[z] + a[z - b], end='')
			b += 2
			z += 1
		for ll in range(k, n):
			print(a[ll], end='')
	else:
		z = k // 2
		b = 2
		print(a[z], end='')
		z += 1
		while z < k:
			print(a[z] + a[z - b], end='')
			b += 2
			z += 1
		for ll in range(k, n):
			print(a[ll], end='')
	print()


t = int(input())
while t:
	(n, k) = map(int, input().split())
	s = input()
	s1 = ''
	if k % 2 != 0:
		s1 += s[k // 2]
		i = k // 2 + 1
		j = k // 2 - 1
	else:
		i = k // 2
		j = k // 2 - 1
	while j >= 0 and i < k:
		s1 += s[i]
		s1 += s[j]
		i += 1
		j -= 1
	s1 += s[k:]
	print(s1)
	t -= 1


for t in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	s = input()
	original_right = s[k:]
	tl = s[:k]
	sl = ''
	l = 0
	r = k - 1
	steps = k
	while l != r > 0:
		sl += tl[l]
		if l < r:
			l += 1
		else:
			l -= 1
		(l, r) = (r, l)
	sl += tl[l]
	print(sl[::-1] + original_right)


import string

def reverse(string, i, j, n):
	if i > n / 2:
		return string
	else:
		temp = string[i]
		string[i] = string[j]
		string[j] = temp
		return reverse(string, i + 1, j - 1, n)
t = int(input())
for b in range(t):
	(n, k) = tuple(map(int, input().split(' ')))
	string = input()
	i = 0
	j = k - 1
	ans = ''
	while i < j:
		ans += string[i]
		ans += string[j]
		i += 1
		j -= 1
	if i == j:
		ans += string[i]
	ans = ans[::-1]
	for idx in range(k, n):
		ans += string[idx]
	print(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	p1 = k // 2
	p2 = p1 + 1
	flag = True
	if k % 2 == 0:
		flag = False
		p1 -= 1
		p2 -= 1
	tmp = k
	while tmp > 0:
		if flag:
			print(s[p1], end='')
			p1 -= 1
			flag = False
		else:
			print(s[p2], end='')
			p2 += 1
			flag = True
		tmp -= 1
	for i in range(k, n):
		print(s[i], end='')
	print()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	word = input()
	p1 = k // 2
	p2 = p1 + 1
	flag = True
	temp = k
	if k % 2 == 0:
		flag = False
		p2 -= 1
		p1 -= 1
	while temp:
		if flag:
			print(word[p1], end='')
			p1 -= 1
			flag = False
		else:
			print(word[p2], end='')
			p2 += 1
			flag = True
		temp -= 1
	for i in range(k, n):
		print(word[i], end='')
	print()


import array as array1
for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	os = list(input())
	(tl, j) = ([], 0)
	myl = array1.array('u', ['s' for x in range(n)])
	for i in range(k, 0, -2):
		myl[int(i - 1)] = os[j]
		j += 1
	if k % 2 == 0:
		start = 1
	else:
		start = 2
	for i in range(start, k, 2):
		myl[i - 1] = os[j]
		j += 1
	for i in range(k + 1, n + 1):
		myl[i - 1] = os[j]
		j += 1
	print(*myl, sep='')


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	ans = ''
	even = 0
	odd = 0
	for j in range(k):
		if j % 2 == 0:
			ans += s[j - even]
			even += 1
		else:
			ans += s[k - j + odd]
			odd += 1
	ans_1 = ans[::-1]
	ans_1 += s[k:]
	print(ans_1)


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	os = list(input())
	(tl, j) = ([], 0)
	myl = [-1 for x in range(n)]
	for i in range(k, 0, -2):
		myl[i - 1] = os[j]
		j += 1
	if k % 2 == 0:
		start = 1
	else:
		start = 2
	for i in range(start, k, 2):
		myl[i - 1] = os[j]
		j += 1
	for i in range(k + 1, n + 1):
		myl[i - 1] = os[j]
		j += 1
	print(*myl, sep='')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(str(input()))[:n]
	narr = []
	i = 0
	j = k - 1
	while i < j:
		narr.append(arr[i])
		narr.append(arr[j])
		i += 1
		j -= 1
	if i == j:
		narr.append(arr[i])
	farr = narr[::-1] + arr[k:n]
	print(''.join(farr))


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	l = input()
	le = []
	ri = []
	r = [None] * m
	if m % 2 == 0:
		ri = l[m // 2:m]
		le = l[m // 2 - 1::-1]
		r[::2] = ri
		r[1::2] = le
		r[m:] = l[m:]
	else:
		ri = l[m // 2 + 1:m]
		le = l[m // 2::-1]
		r[1::2] = ri
		r[::2] = le
		r[m:] = l[m:]
	print(*r, sep='')


t = int(input())
while t > 0:
	t -= 1
	(n, k) = [int(k) for k in input().split(' ')]
	s = str(input())
	rev = s[:k]
	orig = s[k:]
	ans = []
	while len(rev) > 0:
		if len(rev) > 0:
			ans.append(rev[0])
			rev = rev[1:]
		if len(rev) > 0:
			ans.append(rev[-1])
			rev = rev[:-1]
	ans.reverse()
	for c in orig:
		ans.append(c)
	print(''.join(ans))


def rev(x):
	return x[::-1]

def func():
	(n, k) = map(int, input().split())
	s = input()
	l = 0
	r = k - 1
	ans = ''
	while l <= r:
		ans += s[l]
		l += 1
		if l <= r:
			ans += s[r]
			r -= 1
	ans = rev(ans)
	for i in range(k, n):
		ans += s[i]
	print(ans)
t = int(input())
for i in range(t):
	func()