Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well

You are given a binary string $S$ with length $N$ and an integer $K$, which is a divisor of $N$. A string is said to be $K$*-foldable* if it can be changed to a string with length $K$ by repeating the following process without any *collisions* (defined below):
Select the prefix of the current string $S$ with length $2K$. (Note that as long as the length of $S$ is greater than $K$, this prefix always exists.)
For each $i$ ($1 ≤ i ≤ K$), check if the $2K-i+1$-th character of $S$ is equal to the $i$-th character of $S$ ― if they are not equal, there is a collision and the process is invalid.
Erase the prefix of $S$ with length $K$.

Your goal is to reorder the characters of $S$ (possibly leaving this string unchanged) in such a way that the resulting string $S$ is a $K$-foldable string. Find a way to do that or determine that it is impossible. If there are multiple solutions, find the lexicographically smallest rearranged string which is $K$-foldable.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $K$.
The second line contains a single string $S$ with length $N$.

------  Output ------
For each test case, print a single line containing the smallest rearranged string or the string "IMPOSSIBLE" if it is impossible to rearrange $S$.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ K ≤ N ≤ 10^{3}$
$N$ is divisible by $K$
$S$ contains only characters '0' and '1'

----- Sample Input 1 ------ 
2

8 2

00011101

6 2

100111
----- Sample Output 1 ------ 
01100110

IMPOSSIBLE
----- explanation 1 ------ 
Example case 1: If the given string "00011101" is rearranged to "01100110", it becomes $2$-foldable:
- Initially, $S$ is "01100110".
- After the first folding, it becomes "100110".
- After the second folding, it becomes "0110".
- After the third folding, it becomes "10". This string has length $2$, so we are done.

Example case 2: It is impossible to rearrange $S$ into a $2$-foldable string.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Mathematics


Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	o = s.count('1')
	z = n - o
	k = n // k
	if o % k or z % k:
		print('IMPOSSIBLE')
	else:
		word = '1' * (o // k) + '0' * (z // k)
		rev = word[::-1]
		ans = []
		for i in range(k):
			if i & 1:
				ans.append(word)
			else:
				ans.append(rev)
		print(''.join(ans))


for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	S = input()
	n0 = 0
	n1 = 0
	for i in range(N):
		if S[i] == '1':
			n1 += 1
		else:
			n0 += 1
	if n0 % (N // K) == 0 and n1 % (N // K) == 0:
		A = ['0'] * (n0 // (N // K)) + ['1'] * (n1 // (N // K))
		B = ['1'] * (n1 // (N // K)) + ['0'] * (n0 // (N // K))
		ans = []
		for i in range(N // K):
			if i % 2:
				ans += B
			else:
				ans += A
		print(''.join(ans))
	else:
		print('IMPOSSIBLE')


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	x = s.count('1')
	y = s.count('0')
	f = n // k
	if y % f != 0:
		print('IMPOSSIBLE')
		continue
	z = y // f
	ans1 = z * '0' + (k - z) * '1'
	ans = ''
	for j in range(f):
		if j % 2 == 0:
			ans += ans1
			continue
		ans += ans1[::-1]
	print(ans)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split(' '))
	U = input()
	S = N // K
	ans = ''
	Z = U.count('0')
	O = U.count('1')
	ZCount = Z // S
	OCount = O // S
	if Z % S != 0 or O % S != 0:
		print('IMPOSSIBLE')
	elif S != N / K:
		print(''.join(map(str, sorted(U))))
	else:
		for x in range(0, S):
			if x % 2 == 0:
				for y in range(0, ZCount):
					ans += '0'
				for j in range(0, OCount):
					ans += '1'
			else:
				for p in range(0, OCount):
					ans += '1'
				for o in range(0, ZCount):
					ans += '0'
		print(ans)


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 18

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

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

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = get_ints()
	s = input()
	zero = s.count('0')
	one = n - zero
	times = n // k
	if zero % times != 0 or one % times != 0:
		print('IMPOSSIBLE')
		continue
	pat_0 = zero // times
	pat_1 = one // times
	ans = '0' * pat_0 + '1' * pat_1
	pat = ans
	ans += ans[::-1]
	ans *= times // 2
	if times & 1:
		ans += pat
	print(ans)


import sys
import math

def main(arr, K, N):
	freq = {}
	freq[0] = 0
	freq[1] = 0
	for e in arr:
		b = int(e)
		freq[b] += 1
	ans = None
	for i in range(K + 1):
		if i * N / K == freq[0]:
			if (K - i) * (N / K) == freq[1]:
				ans = i
	if ans == None:
		return 'IMPOSSIBLE'
	s = ['0' for i in range(ans)] + ['1' for i in range(K - ans)]
	ans = []
	for j in range(int(N / K)):
		ans += s
		s.reverse()
	return ''.join(ans)
t = int(input())
for i in range(t):
	(N, K) = list(map(int, input().split()))
	arr = input()
	print(main(arr, K, N))


t = int(input())
for _ in range(t):
	(N, K) = map(int, input().split())
	s = input()
	no0 = s.count('0')
	no1 = s.count('1')
	seg = N // K
	count0 = no0 // seg
	count1 = no1 // seg
	if no0 % seg == 0 and no1 % seg == 0:
		for i in range(seg):
			if i % 2 == 0:
				for j in range(count0):
					print(0, end='')
				for j in range(count1):
					print(1, end='')
			else:
				for j in range(count1):
					print(1, end='')
				for j in range(count0):
					print(0, end='')
		print()
	else:
		print('IMPOSSIBLE')


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	ones = 0
	zeros = 0
	for i in s:
		if i == '1':
			ones += 1
		else:
			zeros += 1
	folds = n // k
	if zeros % folds == 0 and ones % folds == 0:
		ans = ''
		for i in range(folds):
			if i % 2 == 0:
				for j in range(zeros // folds):
					ans += '0'
				for j in range(ones // folds):
					ans += '1'
			else:
				for j in range(ones // folds):
					ans += '1'
				for j in range(zeros // folds):
					ans += '0'
		print(ans)
	else:
		print('IMPOSSIBLE')


def count():
	(c1, c2) = (0, 0)
	for ch in s:
		if ch == '1':
			c1 += 1
		else:
			c2 += 1
	return (c1, c2)

def answer():
	(no, nz) = count()
	div = n // k
	if no % div == 0 and nz % div == 0:
		st = ''
		for i in range(div // 2):
			st += '0' * (nz // div) + '1' * (no // div)
			st += '1' * (no // div) + '0' * (nz // div)
		if div & 1:
			st += '0' * (nz // div) + '1' * (no // div)
		return st
	return 'IMPOSSIBLE'
for T in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	print(answer())


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = [0, 0]
	for i in s:
		if i == '0':
			l[0] += 1
		else:
			l[1] += 1
	a = n // k
	o = l[0] // a
	e = l[1] // a
	if l[0] % a == 0 and l[1] % a == 0:
		temp = '0' * o + '1' * e
		ans = ''
		for i in range(a):
			if i % 2 == 0:
				ans = ans + temp
			else:
				ans = ans + temp[::-1]
		print(ans)
	else:
		print('IMPOSSIBLE')


for i in range(int(input())):
	(n, k) = map(int, input().split())
	string = input()
	list1 = [0, 0]
	for i in range(n):
		if string[i] == '0':
			list1[0] += 1
		else:
			list1[1] += 1
	pass1 = n // k
	if list1[0] % pass1 != 0 and list1[1] % pass1 != 0:
		print('IMPOSSIBLE')
	elif len(set(list(string))) == 1:
		print(string)
	else:
		string1 = ''
		string1 += '0' * (list1[0] * k // sum(list1))
		string1 += '1' * (list1[1] * k // sum(list1))
		output = ''
		revs = string1[::-1]
		counter = 0
		while len(output) != n:
			if counter % 2 == 0:
				output += string1
			else:
				output += revs
			counter += 1
		print(output)


t = int(input())
for p in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	s = input()
	z = s.count('0')
	o = s.count('1')
	ns = int(n / k)
	nz = int(z / ns)
	no = int(o / ns)
	if z % ns == 0 and o % ns == 0:
		temp = '0' * nz + '1' * no
		ans = ''
		for i in range(ns):
			if i % 2 == 0:
				ans = ans + temp
			else:
				ans = ans + temp[::-1]
		print(ans)
	else:
		print('IMPOSSIBLE')


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	a = [0] * 2
	for i in s:
		if i == '0':
			a[0] += 1
		else:
			a[1] += 1
	r = n // k
	if n < k or a[0] % r != 0 or a[1] % r != 0:
		print('IMPOSSIBLE')
	else:
		(k0, k1) = (a[0] // r, a[1] // r)
		kstring = ['0'] * k0 + ['1'] * k1
		s1 = []
		for i in range(r):
			s1 += kstring
			kstring.reverse()
		print(''.join(s1))


t = int(input())
for _ in range(t):
	[n, k] = [int(i) for i in input().split()]
	s = str(input())
	(x, y) = (0, 0)
	for i in range(n):
		if s[i] == '0':
			x += 1
		else:
			y += 1
	q = n // k
	if x % q != 0 or y % q != 0:
		print('IMPOSSIBLE')
	else:
		a = '0' * (x // q) + '1' * (y // q)
		b = '1' * (y // q) + '0' * (x // q)
		print((a + b) * (q // 2) + a * (q % 2))


test = int(input())
for _ in range(test):
	(n, k) = map(int, input().split())
	s = input()
	l = [0, 0]
	for i in s:
		l[int(i)] += 1
	j = n // k
	if l[0] % j == 0 and l[1] % j == 0:
		(o, p) = (l[0] // j, l[1] // j)
		s = ''
		e = '0' * o + '1' * p
		f = e[::-1]
		for i in range(j):
			if i % 2 == 0:
				s = s + e
			else:
				s = s + f
		print(s)
	else:
		print('IMPOSSIBLE')


def countChars(s):
	counts = {}
	for c in s:
		counts[c] = counts.setdefault(c, 0) + 1
	return counts

def isPoss(counts, K, N):
	for v in counts.values():
		if v % (N // K):
			return False
	return True

def arrange(counts, K, N):
	baseS = ''
	for k in sorted(counts.keys(), reverse=True):
		v = counts[k]
		baseS += k * (K * v // N)
	out = ''
	for k in range(N // K):
		if k % 2:
			out += baseS
		else:
			out += baseS[::-1]
	return out
T = int(input())
for tc in range(T):
	(N, K) = [int(x) for x in input().split(' ')]
	S = input()
	c = countChars(S)
	if not isPoss(c, K, N):
		print('IMPOSSIBLE')
	else:
		print(arrange(c, K, N))


i = 0
T = int(input())
while i < T:
	(N, K) = map(int, input().split(' '))
	U = input()
	S = N // K
	ans = ''
	Z = U.count('0')
	O = U.count('1')
	ZCount = Z // S
	OCount = O // S
	if Z % S != 0 or O % S != 0:
		print('IMPOSSIBLE')
	else:
		for x in range(0, N // K):
			if x % 2 == 0:
				for y in range(0, ZCount):
					ans += '0'
				for j in range(0, OCount):
					ans += '1'
			else:
				for j in range(0, OCount):
					ans += '1'
				for y in range(0, ZCount):
					ans += '0'
		print(ans)
	i += 1


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	a = input()
	s = n // k
	z = 0
	o = 0
	for i in a:
		if i == '0':
			z += 1
		else:
			o += 1
	if o % s != 0 or z % s != 0:
		print('IMPOSSIBLE')
	else:
		z = z // s
		o = o // s
		b = '0' * z + '1' * o
		k = 0
		l = 0
		c = ''
		while s > 0:
			s -= 1
			if l % 2 == 0:
				c += b
			else:
				c += b[::-1]
			l += 1
		print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	binary_string = input()
	ones = 0
	for i in binary_string:
		ones += 1 & int(i)
	zeros = n - ones
	strk = n // k
	str2k = '0' * (zeros // strk) + '1' * (ones // strk)
	if zeros // strk + ones // strk == k:
		print(((str2k + str2k[::-1]) * (strk // 2 + 1))[:n])
	else:
		print('IMPOSSIBLE')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	b = input()
	bo = 0
	for i in b:
		bo += 1 & int(i)
	bz = n - bo
	bs = n // k
	s = '0' * (bz // bs) + '1' * (bo // bs)
	f = (s + s[::-1]) * (bs // 2 + 1)
	if bz // bs + bo // bs == k:
		print(f[:n])
	else:
		print('IMPOSSIBLE')


from collections import Counter
for _ in range(int(input())):
	(m, n) = map(int, input().split())
	s = input()
	g = Counter(s)
	if n > m or m % n != 0:
		print('IMPOSSIBLE')
	elif g['1'] % (m // n) != 0 or g['0'] % (m // n) != 0:
		print('IMPOSSIBLE')
	else:
		st = ''
		for i in range(g['0'] // (m // n)):
			st += '0'
		for j in range(g['1'] // (m // n)):
			st += '1'
		rev = ''.join(st[::-1])
		u = 0
		v = 0
		for i in range(m // n):
			if u == 0:
				print(st, end='')
				u = 1
				v = 0
			else:
				print(rev, end='')
				v = 1
				u = 0
		print()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	seg = n // k
	ones = s.count('1')
	zeros = s.count('0')
	if ones % seg == 0 and zeros % seg == 0:
		ans = '0' * (zeros // seg) + '1' * (ones // seg)
		ans1 = ans[::-1]
		if n % (2 * k) == 0:
			print((ans + ans1) * (n // (2 * k)))
		else:
			print((ans + ans1) * (n // (2 * k)) + ans)
	else:
		print('IMPOSSIBLE')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	zero = s.count('0')
	one = s.count('1')
	m = n // k
	if zero % m == 0 and zero % m == 0:
		n1 = zero // m
		n2 = one // m
		har = '0' * n1 + '1' * n2
		tess = '1' * n2 + '0' * n1
		final = ''
		for i in range(m):
			if i % 2 == 0:
				final += har
			else:
				final += tess
		print(final)
	else:
		print('IMPOSSIBLE')


from sys import stdin, stdout
from collections import Counter
from itertools import permutations
import bisect
import math
I = lambda : map(int, stdin.readline().split())
I1 = lambda : stdin.readline()
for _ in range(int(I1())):
	(n, k) = I()
	s = I1().strip()
	c0 = s.count('0')
	c1 = s.count('1')
	x = n // k
	if c0 % x != 0 or c1 % x != 0:
		print('IMPOSSIBLE')
	else:
		c0 = c0 // x
		c1 = c1 // x
		s1 = c0 * '0' + c1 * '1'
		s2 = c1 * '1' + c0 * '0'
		c = 1
		s = ''
		while c <= x:
			if c % 2 != 0:
				s += s1
			else:
				s += s2
			c += 1
		print(s)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	s = list(s)
	a = s.count('0')
	b = n - a
	x = n // k
	a1 = a // x
	b1 = b // x
	if a % x != 0 or b % x != 0:
		print('IMPOSSIBLE')
	else:
		s1 = ''
		for j in range(x):
			if j % 2 == 0:
				for m in range(a1):
					s1 = s1 + '0'
				for m in range(b1):
					s1 = s1 + '1'
			else:
				for m in range(b1):
					s1 = s1 + '1'
				for m in range(a1):
					s1 = s1 + '0'
		print(s1)


import sys

def uno():
	return int(sys.stdin.readline().strip())

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

def tres():
	return map(int, sys.stdin.readline().strip().split())
for _ in range(uno()):
	(n, k) = tres()
	s = dos()
	(z, o, ts) = (s.count('0'), s.count('1'), n // k)
	if z % ts or o % ts:
		print('IMPOSSIBLE')
		continue
	ans = ''
	for i in range(ts):
		if i & 1:
			ans += o // ts * '1'
			ans += z // ts * '0'
		else:
			ans += z // ts * '0'
			ans += o // ts * '1'
	print(ans)


def method_1(s, n, k):
	k0 = s.count('0')
	k1 = s.count('1')
	temp = n // k
	if k0 % temp == 0 and k1 % temp == 0:
		res1 = '0' * (k0 // temp) + '1' * (k1 // temp)
	else:
		return 'IMPOSSIBLE'
	ans = ''
	for i in range(temp):
		if i % 2 == 0:
			ans = ans + res1
		else:
			ans = ans + res1[::-1]
	return ans
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(method_1(s, n, k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	n0 = s.count('0')
	n1 = s.count('1')
	fold = n // k
	if n0 % fold == 0 and n1 % fold == 0:
		tr = '0' * (n0 // fold) + '1' * (n1 // fold)
		for i in range(fold):
			if i % 2 == 0:
				print(tr, end='')
			else:
				print(tr[::-1], end='')
		print()
	else:
		print('IMPOSSIBLE')


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	(no_of_ones, no_of_zeros) = (s.count('1'), s.count('0'))
	total_segments = n // k
	result = ''
	if no_of_zeros % total_segments == 0 and no_of_ones % total_segments == 0:
		no_of_ones_per_segment = no_of_ones // total_segments
		no_of_zeros_per_segment = no_of_zeros // total_segments
		for i in range(total_segments):
			if i % 2 == 0:
				for _ in range(no_of_zeros_per_segment):
					result += '0'
				for _ in range(no_of_ones_per_segment):
					result += '1'
			else:
				for _ in range(no_of_ones_per_segment):
					result += '1'
				for _ in range(no_of_zeros_per_segment):
					result += '0'
		print(result)
	else:
		print('IMPOSSIBLE')


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().strip().split(' '))
	s = input()
	g = n // k
	fq = [0] * 2
	for i in range(n):
		fq[ord(s[i]) - ord('0')] += 1
	if fq[0] % g != 0 or fq[1] % g != 0:
		print('IMPOSSIBLE')
	else:
		it = n // k
		f0 = fq[0] // g
		f1 = fq[1] // g
		s1 = ''
		for i in range(f0):
			s1 += '0'
		for j in range(f1):
			s1 += '1'
		s2 = s1[::-1]
		ans = ''
		for i in range(it):
			if i % 2 == 0:
				ans += s1
			else:
				ans += s2
		print(ans)


t = int(input())
for _ in range(t):
	(N, K) = map(int, input().split())
	S = input()
	zeros = 0
	ones = 0
	for i in S:
		if int(i) & 1:
			ones += 1
		else:
			zeros += 1
	rem = N // K
	if ones == N or zeros == N:
		print(S)
	elif ones % rem == 0 and zeros % rem == 0:
		result = ''
		final = ''
		no_ones = ones // rem
		no_zeros = zeros // rem
		for i in range(no_zeros):
			final += '0'
		for i in range(no_ones):
			final += '1'
		for i in range(1, rem + 1):
			if i & 1:
				result += final
			else:
				result += final[-1::-1]
		print(result)
	else:
		print('IMPOSSIBLE')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(zero, one) = (0, 0)
	for i in s:
		if i == '0':
			zero += 1
		else:
			one += 1
	seg = int(n / k)
	if zero % seg != 0 or one % seg != 0:
		print('IMPOSSIBLE')
		continue
	else:
		ans = ''
		ans += '0' * int(zero // seg)
		ans += '1' * int(one // seg)
		f = ''
		for i in range(seg):
			if i % 2 == 0:
				f += ans
			else:
				f += ans[::-1]
		print(f)


t = int(input())
for i in range(t):
	[n, k] = [int(temp) for temp in input().split()]
	s = input()
	_0 = 0
	for j in range(n):
		if s[j] == '0':
			_0 = _0 + 1
	if _0 % (n / k) != 0:
		print('IMPOSSIBLE')
	else:
		temp = ''
		for i in range(int(_0 / (n / k))):
			temp = temp + '0'
		for i in range(int(k - _0 / (n / k))):
			temp = temp + '1'
		for i in range(int(n / k)):
			if i % 2 == 0:
				print(temp, end='')
			else:
				print(temp[::-1], end='')
		print()


try:

	def solve():
		(n, k) = map(int, input().split())
		s = list(map(int, input()))
		segments = int(n / k)
		zerocount = 0
		onecount = 0
		for i in s:
			if i == 0:
				zerocount += 1
			if i == 1:
				onecount += 1
		if zerocount % segments == 0 and onecount % segments == 0:
			zerocount = int(zerocount / segments)
			onecount = int(onecount / segments)
			l = 0
			for l in range(segments):
				if l % 2 == 0:
					print('0' * zerocount, end='')
					print('1' * onecount, end='')
				else:
					print('1' * onecount, end='')
					print('0' * zerocount, end='')
			print(end='\n')
		else:
			print('IMPOSSIBLE')
	i = int(input())
	for j in range(i):
		solve()
except:
	pass


from collections import Counter
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	st = input()
	cnt = Counter(st)
	group = n // k
	for ones in range(0, k + 1):
		no_one = ones * group
		no_zero = (k - ones) * group
		if no_zero == cnt['0'] and no_one == cnt['1']:
			tmp = '0' * (k - ones) + '1' * ones
			tmp2 = tmp[::-1]
			an = (tmp + tmp2) * (group // 2)
			if group % 2 == 1:
				an += tmp
			print(an)
			break
	else:
		print('IMPOSSIBLE')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	z = 0
	o = 0
	for sub in input():
		if sub == '0':
			z += 1
		else:
			o += 1
	r = n // k
	a = 0
	b = 0
	ans = ''
	if not n % k and (not z % r) and (not o % r):
		a = z // r
		b = o // r
	else:
		ans = 'IMPOSSIBLE'
	if ans == '':
		tmp = k
		while tmp > 0:
			tmp -= 1
			if a > 0:
				ans += '0'
				a -= 1
			else:
				ans += '1'
				b -= 1
		r -= 1
		actual = ans
		rev = actual[::-1]
		while r > 0:
			r -= 1
			ans += rev
			(rev, actual) = (actual, rev)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	se = {'0': 0, '1': 0}
	for c in s:
		if c == '0':
			se['0'] += 1
		else:
			se['1'] += 1
	(x, y) = (int(se['0'] / (n // k)), int(se['1'] / (n // k)))
	if x + y - k:
		print('IMPOSSIBLE')
	elif n - k:
		res = x * '0' + y * '1'
		res += y * '1' + x * '0'
		if n // k % 2:
			res += res * (n // (2 * k) - 1) + x * '0' + y * '1'
		else:
			res += res * (n // (2 * k) - 1)
		print(res)
	else:
		print(x * '0' + y * '1')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	string = input()
	zeroCount = string.count('0')
	oneCount = string.count('1')
	noSeg = n // k
	if zeroCount % noSeg == 0 and oneCount % noSeg == 0:
		for i in range(1, noSeg + 1):
			if i % 2:
				for j in range(1, zeroCount // noSeg + 1):
					print(0, end='')
				for j in range(1, oneCount // noSeg + 1):
					print(1, end='')
			else:
				for j in range(1, oneCount // noSeg + 1):
					print(1, end='')
				for j in range(1, zeroCount // noSeg + 1):
					print(0, end='')
		print()
	else:
		print('IMPOSSIBLE')


try:
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		s = input()
		a = 0
		b = 0
		for i in range(len(s)):
			if s[i] == '0':
				a += 1
			else:
				b += 1
		c = n // k
		if a % c == 0 and b % c == 0:
			e = a // c
			f = b // c
			even = ''
			odd = ''
			total = ''
			for i in range(e):
				even += '0'
			for i in range(f):
				odd += '1'
				even += '1'
			for i in range(e):
				odd += '0'
			for i in range(1, c + 1):
				if i % 2 != 0:
					total += even
				else:
					total += odd
			print(total)
		else:
			print('IMPOSSIBLE')
except:
	Exception


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	s = input()
	a = 0
	b = 0
	c = n // k
	for i in range(len(s)):
		if s[i] == '0':
			a += 1
		else:
			b += 1
	if a % c == 0 and b % c == 0:
		e = a // c
		f = b // c
		ans1 = ''
		ans2 = ''
		ans = ''
		for i in range(e):
			ans1 += '0'
		for i in range(f):
			ans1 += '1'
			ans2 += '1'
		for i in range(e):
			ans2 += '0'
		for i in range(1, c + 1):
			if i % 2 != 0:
				ans += ans1
			else:
				ans += ans2
		print(ans)
	else:
		print('IMPOSSIBLE')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	S = input()
	knd = n // k
	d = {'0': 0, '1': 0}
	for ele in S:
		d[ele] += 1
	if d['0'] % knd != 0 or d['1'] % knd != 0:
		print('IMPOSSIBLE')
	else:
		p = d['0'] // knd
		q = d['1'] // knd
		ans = ''
		fu = '0' * p + '1' * q
		su = '1' * q + '0' * p
		i = 1
		while knd:
			knd -= 1
			if i % 2 == 1:
				ans += fu
			else:
				ans += su
			i += 1
		print(ans)


T = int(input())
for j in range(T):
	(N, K) = map(int, input().split())
	S = input()
	ans = str()
	Z = O = 0
	for e in S:
		if e == '0':
			Z += 1
		else:
			O += 1
	a = N // K
	if Z % a != 0:
		print('IMPOSSIBLE')
		continue
	z = Z // a
	o = O // a
	f = str()
	l = str()
	for i in range(z):
		f += '0'
	for i in range(o):
		l += '1'
	first = f + l
	last = l + f
	for i in range(a):
		if i % 2 == 0:
			ans += first
		else:
			ans += last
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	count_1 = s.count('1')
	count_0 = s.count('0')
	num_of_seg = n // k
	if count_1 % num_of_seg == 0 and count_0 % num_of_seg == 0:
		for x in range(num_of_seg):
			if x % 2 == 0:
				for y in range(count_0 // num_of_seg):
					print('0', end='')
				for y in range(count_1 // num_of_seg):
					print('1', end='')
			else:
				for y in range(count_1 // num_of_seg):
					print('1', end='')
				for y in range(count_0 // num_of_seg):
					print('0', end='')
		print()
	else:
		print('IMPOSSIBLE')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(one, zero) = (0, 0)
	for x in s:
		if x == '1':
			one += 1
		else:
			zero += 1
	if one == 0 or zero == 0:
		print(s)
	else:
		(ans, zc) = ('', -1)
		kset = n // k
		for i in range(1, k):
			if zero == kset * i:
				zc = i
				break
		if zc == -1:
			print('IMPOSSIBLE')
		else:
			(af, rs) = ('', '')
			for i in range(1, k + 1):
				if i > zc:
					af += '1'
				else:
					af += '0'
			rs = af[::-1]
			for i in range(kset):
				if i % 2 == 0:
					ans += af
				else:
					ans += rs
			print(ans)


from collections import Counter
for i in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	s = Counter(s)
	x = n // k
	if s['0'] % x != 0 and s['1'] % x != 0:
		print('IMPOSSIBLE')
		continue
	for i in range(x):
		print('0' * (s['0'] // x) + '1' * (s['1'] // x), end='') if i % 2 == 0 else print('1' * (s['1'] // x) + '0' * (s['0'] // x), end='')
	print()


t = int(input())
while t:
	(n, k) = map(int, input().split())
	s = input()
	ans = ''
	ans1 = ''
	finans = ''
	set_len = int(len(s) / k)
	count_1 = 0
	count_0 = 0
	for i in s:
		if i == '1':
			count_1 += 1
		else:
			count_0 += 1
	if count_1 % set_len == 0:
		if count_0 % set_len == 0:
			set_1 = int(count_1 / set_len)
			set_0 = int(count_0 / set_len)
			for i in range(set_0):
				ans += '0'
			for i in range(set_1):
				ans += '1'
			ans1 = ans[::-1]
			for i in range(set_len):
				if i % 2 == 0:
					finans += ans
				else:
					finans += ans1
			print(finans)
		else:
			print('IMPOSSIBLE')
	else:
		print('IMPOSSIBLE')
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	seg = n // k
	if s.count('0') % seg != 0 or s.count('1') % seg != 0:
		print('IMPOSSIBLE')
	else:
		for i in range(seg):
			if i % 2 == 0:
				for j in range(s.count('0') // seg):
					print('0', end='')
				for k in range(s.count('1') // seg):
					print('1', end='')
			else:
				for j in range(s.count('1') // seg):
					print('1', end='')
				for k in range(s.count('0') // seg):
					print('0', end='')
	print()


MOD = 1000000007
from collections import defaultdict as dd, Counter, deque

def si():
	return input()

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

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

def mi():
	return map(int, input().split())

def out(v):
	print(v)

def spout():
	print(v, end=' ')

def d2b(n):
	return bin(n).replace('0b', '')

def twod(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def vow():
	return ['a', 'e', 'i', 'o', 'u']

def let():
	return [chr(i) for i in range(97, 123)]

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

def ispow2(x):
	return x and (not x & x - 1)

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return list(factors)
t = ii()
while t:
	t -= 1
	(n, k) = mi()
	s = list(si())
	(x, y) = (s.count('0'), s.count('1'))
	d = n // k
	if x % d != 0 or y % d != 0:
		print('IMPOSSIBLE')
		continue
	a = '0' * (x // d) + '1' * (y // d)
	for i in range(d):
		if i % 2 == 0:
			print(a, end='')
		else:
			print(a[::-1], end='')
	print('')


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve(n, k, string):
	zero = 0
	one = 0
	repeat = n // k
	for i in range(len(string)):
		if string[i] == '0':
			zero += 1
		else:
			one += 1
	if zero % repeat != 0 or one % repeat != 0:
		return 'IMPOSSIBLE'
	else:
		res = ''
		a1 = zero // repeat
		a2 = one // repeat
		lexi = a1 * '0' + a2 * '1'
		le = a2 * '1' + a1 * '0'
		count = 1
		while repeat:
			repeat -= 1
			if count % 2 == 1:
				res += lexi
			else:
				res += le
			count += 1
		return res
for _ in range(inp()):
	(n, k) = map(int, input().split(' '))
	string = insr()
	print(solve(n, k, string))


testcase = int(input())
for _ in range(testcase):
	li = [0, 0]
	(n, k) = map(int, input().split())
	s = input()
	for i in range(n):
		li[int(s[i])] += 1
	if li[0] % (n / k) != 0 or li[1] % (n / k) != 0:
		print('IMPOSSIBLE')
		continue
	if li[0] == n or li[1] == n:
		print(s)
		continue
	li[0] = li[0] // (n / k)
	li[1] = li[1] // (n / k)
	ans = []
	for i in range(int(li[0])):
		ans.append('0')
	for i in range(int(li[1])):
		ans.append('1')
	temp = ans[:]
	for i in range(n // k - 1):
		temp = temp[::-1]
		ans = ans + temp
	print(''.join(ans))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(zeros, ones) = (s.count('0'), s.count('1'))
	d = n // k
	if zeros % d != 0 or ones % d != 0:
		print('IMPOSSIBLE')
		continue
	else:
		str = ''
		str += ''.join('0' * (zeros // d))
		str += ''.join('1' * (ones // d))
		ans = ''
		k1 = 0
		while k1 < n / k:
			if k1 % 2 == 0:
				ans += str
			else:
				ans += ''.join(reversed(str))
			k1 += 1
		print(ans)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	flag = 0
	if k > n:
		flag = 1
	if n % k != 0:
		flag = 1
	t = 0
	for i in range(n):
		if s[i] == '0':
			t += 1
	if t % (n // k) != 0 or (n - t) % (n // k) != 0:
		flag = 1
	if flag == 1:
		print('IMPOSSIBLE')
	else:
		l = ''
		for j in range(n // k):
			if j % 2 == 0:
				l += '0' * (t // (n // k)) + '1' * ((n - t) // (n // k))
			else:
				l += '1' * ((n - t) // (n // k)) + '0' * (t // (n // k))
		print(l)


t = int(input())
while t:
	(n, k) = map(int, input().split())
	s = input()
	(i, j) = (s.count('1'), s.count('0'))
	p = ''
	q = ''
	a = ''
	if i % (n / k):
		print('IMPOSSIBLE')
	else:
		for m in range(int(j / (n / k))):
			p += '0'
		for b in range(int(i / (n / k))):
			p += '1'
		for o in p:
			q = o + q
		for r in range(1, int(n / k) + 1):
			if r % 2 == 1:
				a = a + p
			else:
				a = a + q
		print(a)
	t = t - 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	z = 0
	o = 0
	for i in range(n):
		if s[i] == '0':
			z = z + 1
		else:
			o = o + 1
	if z % (n // k) > 0 or o % (n // k) > 0:
		print('IMPOSSIBLE')
	else:
		a = z // (n // k)
		b = o // (n // k)
		s2 = ''
		for i in range(a):
			s2 = s2 + '0'
		for i in range(b):
			s2 = s2 + '1'
		ans = ''
		for i in range(n // k):
			ans = ans + s2
			s2 = s2[::-1]
		print(ans)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = input()
	c = n // k
	z1 = s.count('0')
	z2 = z1 // c
	o1 = s.count('1')
	o2 = o1 // c
	if z1 == n or o1 == n:
		print(s)
	elif z1 % c != 0 or o1 % c != 0:
		print('IMPOSSIBLE')
	else:
		a = '0' * z2 + '1' * o2
		ans = ''
		for i in range(c):
			if i % 2 == 0:
				ans += a
			else:
				ans += a[::-1]
		print(ans)


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	s = input()
	f = defaultdict(int)
	for i in s:
		f[i] += 1
	c = n // k
	z1 = f['0']
	z2 = z1 // c
	o1 = f['1']
	o2 = o1 // c
	if z1 == n or o1 == n:
		print(s)
	elif z1 % c != 0 or o1 % c != 0:
		print('IMPOSSIBLE')
	else:
		a = '0' * z2 + '1' * o2
		b = a[::-1]
		ans = ''
		for i in range(c):
			if i % 2 == 0:
				ans += a
			else:
				ans += b
		print(ans)


import sys
import math
from collections import defaultdict
mod = 1000000007
T = 1
T = int(sys.stdin.readline())
for _ in range(T):
	(n, k) = map(int, input().split())
	s = input()
	ones = s.count('1')
	zeros = n - ones
	y = n // k
	if ones % y == 0 and zeros % y == 0:
		p = zeros // y
		q = ones // y
		ansx = '0' * p
		ansx = ansx + '1' * q
		ans = ansx + ansx[::-1]
		ans = ans * (n // (k << 1))
		if n % (k << 1):
			ans += ansx
		print(ans)
	else:
		print('IMPOSSIBLE')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	zero = s.count('0')
	one = s.count('1')
	val = n // k
	if zero % val != 0 or one % val != 0:
		print('IMPOSSIBLE')
	else:
		v1 = zero // val
		v2 = one // val
		for i in range(val):
			if i % 2 == 0:
				print(v1 * '0' + v2 * '1', end='')
			else:
				print(v2 * '1' + v1 * '0', end='')
		print('')


import os
t = int(input(''))
for _ in range(t):
	(n, k) = map(int, input('').split(' '))
	temp = n // k
	count_0 = 0
	count_1 = 0
	input_string = input('')
	for char in input_string:
		if char == '0':
			count_0 += 1
	count_1 = len(input_string) - count_0
	if count_0 % temp == 0 and count_1 % temp == 0:
		a = '0' * (count_0 // temp)
		b = '1' * (count_1 // temp)
		k_string = a + b
		k_string_reverse = k_string[::-1]
		res = ''
		for i in range(temp):
			if i % 2 == 0:
				res += k_string
			else:
				res += k_string_reverse
		print(res)
	else:
		print('IMPOSSIBLE')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	string = input()
	cou1 = string.count('1')
	cou0 = n - cou1
	if cou1 == 0 or cou0 == 0:
		print(string)
	else:
		val = n // k
		i = 1
		ans = []
		if cou0 % val != 0 or cou1 % val != 0:
			print('IMPOSSIBLE')
		else:
			cou1 = cou1 // val
			cou0 = cou0 // val
			for i in range(k):
				if cou0 > 0:
					ans.append('0')
					cou0 -= 1
				else:
					ans.append('1')
					cou1 -= 1
			round = 1
			cou = k - 1
			for i in range(k, n):
				if round == 1:
					ans.append(ans[cou])
					cou -= 1
					if cou < 0:
						cou = 0
						round = 0
				elif round == 0:
					ans.append(ans[cou])
					cou += 1
					if cou == k:
						cou = k - 1
						round = 1
			print(''.join(ans))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	no_of_seg = n // k
	zeros = 0
	ones = 0
	for i in s:
		if i == '0':
			zeros += 1
		else:
			ones += 1
	if zeros % no_of_seg != 0 or ones % no_of_seg != 0:
		print('IMPOSSIBLE')
		continue
	zeros = zeros // no_of_seg
	ones = ones // no_of_seg
	res = ''
	for i in range(no_of_seg):
		temp = ''
		if i % 2 == 0:
			for j in range(zeros):
				temp += '0'
			for j in range(ones):
				temp += '1'
		else:
			for j in range(ones):
				temp += '1'
			for j in range(zeros):
				temp += '0'
		res += temp
	print(res)


t = int(input())
for i in range(t):
	x = input()
	x = x.split()
	n = int(x[0])
	k = int(x[1])
	s = input()
	factor = n // k
	n0 = s.count('0')
	n1 = s.count('1')
	if n0 % factor != 0 or n1 % factor != 0:
		print('IMPOSSIBLE')
	else:
		r = '0' * (n0 // factor) + '1' * (n1 // factor)
		rr = r[-1::-1]
		p = ''
		for i in range(factor):
			if i % 2 == 0:
				p += r
			else:
				p += rr
		print(p)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(input())
	d = {'0': 0, '1': 0}
	for x in s:
		d[x] += 1
	seg = n // k
	if d['0'] % seg != 0 or d['1'] % seg != 0:
		print('IMPOSSIBLE')
	else:
		p = d['0'] // seg
		q = d['1'] // seg
		pre = '0' * p + '1' * q
		suf = '1' * q + '0' * p
		i = 0
		ans = ''
		while seg:
			seg -= 1
			if i % 2 == 0:
				ans += pre
			else:
				ans += suf
			i += 1
		print(ans)


def find(n, k, s):
	repeat = n // k
	zero = 0
	one = 0
	for i in s:
		if i == '0':
			zero += 1
		else:
			one += 1
	li = []
	for i in range(0, k + 1):
		z = i
		o = k - i
		if z * repeat == zero and o * repeat == one:
			temp = ''
			str1 = '0' * z + '1' * o
			str2 = '1' * o + '0' * z
			for m in range(repeat):
				if m % 2 == 0:
					temp += str1
				else:
					temp += str2
			li.append(temp)
			temp = ''
			for m in range(repeat):
				if m % 2 == 0:
					temp += str2
				else:
					temp += str1
			li.append(temp)
	if len(li) == 0:
		return 'IMPOSSIBLE'
	else:
		li.sort()
		return li[0]
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	print(find(n, k, s))


def kfolded(s, k):
	n = len(s)
	if n == 0:
		return 'IMPOSSIBLE'
	c1 = 0
	c2 = 0
	seg = n // k
	for c in s:
		if c == '0':
			c1 += 1
		else:
			c2 += 1
	if c1 == 0 or c2 == 0:
		return s
	if c1 % seg == 0 and c2 % seg == 0 and (c1 // seg != 0) and (c2 // seg != 0):
		num1 = c1 // seg
		num2 = c2 // seg
	else:
		return 'IMPOSSIBLE'
	seg1 = ['0'] * num1
	seg2 = ['1'] * num2
	p1 = ''.join(seg1 + seg2)
	p2 = ''.join(seg2 + seg1)
	if seg == 1:
		return p1
	ans = []
	for i in range(seg // 2):
		ans.append(p1)
		ans.append(p2)
	if seg % 2 != 0:
		ans.append(p1)
	return ans
t = int(input())
for i in range(t):
	nk = input().strip().split()
	n = int(nk[0])
	k = int(nk[1])
	s = input()
	result = kfolded(s, k)
	print(''.join(result))


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	a = input()
	t0 = 0
	t1 = 0
	for i in a:
		if int(i):
			t1 += 1
		else:
			t0 += 1
	b = t0 * k // n
	c = t1 * k // n
	if b + c == k:
		ss = '0' * b + '1' * c
		for i in range(n // k):
			if i % 2:
				print(ss[::-1], end='')
			else:
				print(ss, end='')
		print()
	else:
		print('IMPOSSIBLE')


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = input()
	x = c.count('1')
	y = c.count('0')
	z = a // b
	d = x // z
	e = y // z
	f = ''
	h = ''
	j = 0
	if y % z != 0 or x % z != 0:
		print('IMPOSSIBLE')
	else:
		f = '0' * e + '1' * d
		g = f[::-1]
		for i in range(z):
			if j == 0:
				h = h + f
				j = 1
				continue
			if j == 1:
				h = h + g
				j = 0
		print(h)


def k_fold_string(string: list, n, k):
	counts = [string.count('0'), string.count('1')]
	if counts[0] % (n // k) != 0 and counts[1] % (n // k) != 0:
		return 'IMPOSSIBLE'
	else:
		pattern = ['0' * (counts[0] // (n // k)) + '1' * (counts[1] // (n // k)), '1' * (counts[1] // (n // k)) + '0' * (counts[0] // (n // k))]
		count = 0
		ans = ''
		while count != n // k:
			if count % 2 == 0:
				ans += pattern[0]
			else:
				ans += pattern[1]
			count += 1
		return ans
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	string = input()
	print(k_fold_string(string, n, k))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = [int(i) for i in s]
	zero = a.count(0)
	one = a.count(1)
	m = n // k
	if zero % m != 0 or one % m != 0:
		print('IMPOSSIBLE')
	else:
		ans = ''
		e = zero // m
		p = one // m
		while e:
			ans += '0'
			e -= 1
		while p:
			ans += '1'
			p -= 1
		m -= 1
		temp = ans[::-1]
		while m:
			ans += temp
			temp = temp[::-1]
			m -= 1
		print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	(zero, one) = (0, 0)
	for (i, j) in enumerate(s):
		if j == '0':
			zero += 1
		else:
			one += 1
	ans = 'IMPOSSIBLE'
	if zero % (n // k) == 0:
		ans = zero // (n // k) * '0' + one // (n // k) * '1'
		for i in range(n // k):
			print(ans, end='')
			ans = ans[::-1]
		print()
	else:
		print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	l = []
	l1 = []
	a = n // k
	if s.count('0') % a != 0 or s.count('1') % a != 0:
		print('IMPOSSIBLE')
	else:
		n0 = s.count('0') // a
		n1 = s.count('1') // a
		while n0 != 0:
			l.append('0')
			n0 = n0 - 1
		while n1 != 0:
			l.append('1')
			n1 = n1 - 1
		s1 = ''.join(l)
		for k in range(1, a + 1):
			if k % 2 != 0:
				l1.append(s1)
			else:
				l1.append(s1[::-1])
		print(''.join(l1))


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = input()
	if s.count('0') % (n / k) != 0 or s.count('1') % (n / k) != 0:
		print('IMPOSSIBLE')
	else:
		l = ''
		f = 0
		while True:
			l += '0' * int(s.count('0') // (n / k)) + '1' * int(s.count('1') // (n / k))
			if len(l) >= n:
				break
			l += '1' * int(s.count('1') // (n / k)) + '0' * int(s.count('0') // (n / k))
			if len(l) >= n:
				break
		print(l)


from sys import stdin, stdout, setrecursionlimit
from math import gcd, ceil, sqrt
from collections import Counter, deque
from bisect import bisect_left, bisect_right
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007
tc = ii1()
for _ in range(tc):
	(n, k) = iia()
	s = is1()
	d = Counter(s)
	x = n // k
	if d['1'] % x != 0 or d['0'] % x != 0:
		print('IMPOSSIBLE')
	else:
		one = d['1'] // x
		zero = d['0'] // x
		res = ''
		for i in range(x):
			if i % 2 == 0:
				res += '0' * zero + '1' * one
			else:
				res += '1' * one + '0' * zero
		print(res)


def solve(n, k, s):
	one = s.count('1')
	zero = s.count('0')
	folds = n // k
	if zero % folds != 0 or one % folds != 0:
		return 'IMPOSSIBLE'
	else:
		n1 = one // folds
		n0 = zero // folds
		s = '0' * n0 + '1' * n1
		t = s[::-1]
		c = 1
		res = ''
		while c <= folds:
			if c % 2 != 0:
				res += s
			else:
				res += t
			c += 1
		return res
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	s = input()
	print(solve(n, k, s))


for t in range(int(input())):
	a = input().split()
	(n, k) = (int(a[0]), int(a[1]))
	k = int(n / k)
	a = input()
	x = a.count('0')
	y = a.count('1')
	if x % k != 0 or y % k != 0:
		print('IMPOSSIBLE')
	else:
		(x, y) = (int(x / k), int(y / k))
		a = [0 for i in range(x)] + [1 for i in range(y)]
		for i in range(k):
			if i % 2 == 0:
				print(*a, sep='', end='')
			else:
				print(*a[::-1], sep='', end='')
		print('')


def kfold(n, k, s):
	zero = 0
	one = 0
	segment_count = n // k
	for i in s:
		if i == '0':
			zero += 1
		else:
			one += 1
	if zero % segment_count != 0 or one % segment_count != 0:
		return 'IMPOSSIBLE'
	zero = zero // segment_count
	one = one // segment_count
	ans = ''
	x = 1
	while x <= segment_count:
		if x % 2 == 1:
			for _ in range(0, zero):
				ans = ans + '0'
			for _ in range(0, one):
				ans = ans + '1'
		else:
			for _ in range(0, one):
				ans = ans + '1'
			for _ in range(0, zero):
				ans = ans + '0'
		x += 1
	return ans
t = int(input())
while t:
	(n, k) = list(map(int, input().split()))
	s = input()
	ans = kfold(n, k, s)
	print(ans)
	t -= 1


def gcd(x, y):
	if x > y:
		small = y
	else:
		small = x
	for i in range(1, small + 1):
		if x % i == 0 and y % i == 0:
			gcd = i
	return gcd

def pal(s, n):
	k = 0
	for i in range(int(n / 2)):
		if s[i] == s[n - i]:
			k += 1
	if k == int(n / 2):
		return True
	else:
		return False
t = int(input())
while t:
	(n, k) = map(int, input().strip().split(' '))
	s = input()
	o = 0
	z = 0
	j = list()
	for i in range(1, 50):
		j.append(2 ** i)
	for i in range(n):
		if s[i] == '1':
			o += 1
		else:
			z += 1
	if o < 1 or z < 1:
		print(s)
	else:
		g = gcd(o, z)
		x = int(o / g)
		y = int(z / g)
		if k % (x + y) != 0:
			print('IMPOSSIBLE')
		else:
			a = ''
			d = int(k / (x + y))
			for i in range(y * d):
				a = a + '0'
			for i in range(x * d):
				a = a + '1'
			p = k
			j = 1
			b = a
			while p < n:
				if j % 2 != 0:
					a += b[::-1]
				else:
					a += b
				p += k
				j += 1
			print(a)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	d = dict()
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	no_zero = d.get('0', 0)
	no_ones = d.get('1', 0)
	m = n // k
	if no_ones % m != 0 or no_ones % m != 0:
		print('IMPOSSIBLE')
	else:
		f = ''
		x_0 = no_zero // m
		y_1 = no_ones // m
		for i in range(x_0):
			f = f + '0'
		for i in range(y_1):
			f = f + '1'
		s1 = ''
		for i in range(m):
			if i % 2 == 0:
				s1 = s1 + f
			else:
				s1 = s1 + f[::-1]
		print(s1)