Given a string and number of rows ‘n’. Print the string formed by concatenating n rows when the input string is written in row-wise Zig-Zag fashion.
Example 1:
Input: 
str = "ABCDEFGH"
n = 2
Output: "ACEGBDFH"
Explanation: 
Let us write input string in 
Zig-Zag fashion in 2 rows.
A   C   E   G  
  B   D   F   H
Now concatenate the two rows and ignore 
spaces in every row. We get "ACEGBDFH"
Example 2:
Input: 
str = "GEEKSFORGEEKS"
n = 3
Output: GSGSEKFREKEOE
Explanation: 
Let us write input string in 
Zig-Zag fashion in 3 rows.
G       S       G       S
  E   K   F   R   E   K
    E       O       E
Now concatenate the two rows and ignore spaces
in every row. We get "GSGSEKFREKEOE"
Your Task:
You need not read input or print anything. Your task is to complete the function convert() which takes 2 arguments(string str, integer n) and returns the resultant string.
Expected Time Complexity: O(|str|).
Expected Auxiliary Space: O(|str|).
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:

    def convert(self, Str, n):
        # code here

Solutions:
class Solution:

	def convert(self, Str, n):
		row = 0
		direction = 1
		output = [''] * n
		for char in Str:
			output[row] = output[row] + char
			if row < n - 1 and direction == 1:
				row += 1
			elif row > 0 and direction == -1:
				row -= 1
			else:
				direction *= -1
				row += direction
		return ''.join(output)


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		arr = [''] * n
		(row, isDown) = (0, True)
		for char in Str:
			arr[row] += char
			if isDown:
				row += 1
			else:
				row -= 1
			if row == n - 1:
				isDown = False
			elif row == 0:
				isDown = True
		return ''.join(arr)


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		l = [''] * n
		k = 0
		j = 1
		h = 1
		for i in range(len(Str)):
			if k == 0:
				l[k] = l[k] + Str[i]
				j = 1
				h = 0
				k += 1
			elif k == n - 1:
				l[k] = l[k] + Str[i]
				k -= 1
				j = 0
				h = 1
			elif j == 1:
				l[k] += Str[i]
				k += 1
			elif h == 1:
				l[k] += Str[i]
				k -= 1
		return ''.join(l)


class Solution:

	def convert(self, s, n):
		if n == 1:
			return s
		st = 2 * n - 2
		copy = st
		Len = len(s)
		k = 0
		ans = ''
		while k < n:
			sub = ''
			i = k
			f = 0
			while i < Len:
				sub += s[i]
				if k == 0 or k == n - 1:
					i += st
				elif f == 0:
					i += st - 2 * k
					f = 1
				else:
					i += 2 * k
					f = 0
			ans += sub
			k += 1
		return ans


class Solution:

	def convert(self, Str, n):
		if n == 1 or len(Str) <= n:
			return Str
		ans = [''] * n
		(idx, step) = (0, 1)
		for ch in Str:
			ans[idx] += ch
			if idx == 0:
				step = 1
			if idx == n - 1:
				step = -1
			idx += step
		return ''.join(ans)


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		ans = [[] for _ in range(n)]
		i = 0
		step = 1
		for c in Str:
			ans[i].append(c)
			i += step
			if i == n - 1:
				step = -1
			elif i == 0:
				step = 1
		return ''.join((''.join(ans[i]) for i in range(n)))


class Solution:

	def convert(self, Str, n):
		s = Str
		if n < 2:
			return Str
		str_list = [''] * n
		ans = ''
		row = 0
		change = 1
		for i in range(len(s)):
			str_list[row] += s[i]
			if row == 0:
				change = 1
			elif row == n - 1:
				change = -1
			row += change
		ans = ''.join(str_list)
		return ans


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		res = {}
		for i in range(n):
			res[i] = []
		i = 0
		row = 0
		flag = 1
		while True:
			if flag:
				while row < n and i < len(Str):
					res[row].append(Str[i])
					i += 1
					row += 1
				row = n - 2
			else:
				while row >= 0 and i < len(Str):
					res[row].append(Str[i])
					row -= 1
					i += 1
				row = 1
			flag = not flag
			if i >= len(Str):
				break
		ans = []
		for i in res:
			ans += res[i]
		ans = ''.join(ans)
		return ans


class Solution:

	def convert(self, Str, n):
		s = ''
		k = 0
		if n == 1:
			return Str
		for i in range(n):
			flag = 0
			if i == 0 or i == n - 1:
				for j in range(i, len(Str), 2 * n - 2):
					s = s + Str[j]
			else:
				j = i
				while j <= len(Str) - 1:
					s = s + Str[j]
					if flag == 0:
						j = j + 2 * (n - i) - 2
						flag = 1
					else:
						j = j + 2 * i
						flag = 0
		return s


class Solution:

	def convert(self, s, n):
		ind = []
		if n == 1:
			return s
		for i in range(0, len(s), 2 * n - 2):
			ind.append(i)
		t = len(ind)
		last = i + 2 * n - 2
		i = 1
		while i < n:
			k = 0
			while k < t - 1:
				if ind[k] + i != ind[k + 1] - i:
					ind.append(ind[k] + i)
					ind.append(ind[k + 1] - i)
				else:
					ind.append(ind[k] + i)
				k += 1
			if ind[k] + i < len(s):
				ind.append(ind[k] + i)
				if last - i < len(s) and ind[k] + i != last - i:
					ind.append(last - i)
			i += 1
		ans = ''
		for i in ind:
			ans += s[i]
		return ans


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		s = [''] * n
		cycle = 2 * (n - 1)
		for i in range(len(Str)):
			j = min(i % cycle, (cycle - i) % cycle)
			s[j] += Str[i]
		return ''.join(s)


class Solution:

	def convert(self, Str, n):
		l = len(Str)
		if n == 1:
			return Str
		row = 0
		arr = ['' for i in range(l)]
		for i in range(l):
			arr[row] += Str[i]
			if row == n - 1:
				down = False
			elif row == 0:
				down = True
			if down == True:
				row += 1
			else:
				row -= 1
		return ''.join(arr)


class Solution:

	def convert(self, s, n):
		if n == 1:
			return s
		output = ['' for _ in range(n)]
		add = True
		i = 0
		for item in s:
			output[i] += item
			if add:
				i += 1
			else:
				i -= 1
			if i == n - 1:
				add = False
			if i == 0:
				add = True
		return ''.join(output)


class Solution:

	def convert(self, Str, n):
		ans = [''] * (n + 1)
		down = True
		j = 0
		if n == 1:
			return Str
		for i in range(0, len(Str)):
			ans[j] += Str[i]
			if down == True:
				if j == n - 1:
					j -= 1
					down = False
				else:
					j += 1
			elif j == 0:
				j += 1
				down = True
			else:
				j -= 1
		res = ''
		for i in range(0, len(ans)):
			res += ans[i]
		return res


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		strRows = ['' for x in range(n + 1)]
		counter = 0
		dirUp = False
		for i in Str:
			strRows[counter] += i
			if counter == n - 1:
				dirUp = True
			if counter == 0:
				dirUp = False
			if dirUp:
				counter -= 1
			else:
				counter += 1
		finalStr = ''
		for i in strRows:
			finalStr += i
		return finalStr


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		l = len(Str)
		a = ['' for x in range(n)]
		row = 0
		for i in range(l):
			a[row] += Str[i]
			if row == n - 1:
				down = False
			elif row == 0:
				down = True
			if down:
				row += 1
			else:
				row -= 1
		op = ''
		for i in range(n):
			op += a[i]
		return op


class Solution:

	def convert(self, s, numRows):
		if numRows == 1:
			return s
		res = ''
		for r in range(numRows):
			increment = (numRows - 1) * 2
			for i in range(r, len(s), increment):
				res += s[i]
				if r > 0 and r < numRows - 1 and (i + increment - 2 * r < len(s)):
					res += s[i + increment - 2 * r]
		return res


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		arr = ['' for _ in range(n)]
		index = 0
		for x in Str:
			arr[index] = arr[index] + x
			if index == 0:
				step = 1
			elif index == n - 1:
				step = -1
			index += step
		return ''.join(arr)


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		arr = []
		for _ in range(n):
			arr.append('')
		row = 0
		down = True
		for i in Str:
			if row >= 0:
				arr[row] += i
			if row == 0:
				down = True
			if row == n - 1:
				down = False
			if not down:
				row -= 1
			else:
				row += 1
		return ''.join(arr)


class Solution:

	def convert(self, Str, n):
		s = ['' for i in range(n)]
		(i, j, x) = (0, 0, 1)
		while i < len(Str):
			s[j] += Str[i]
			if j == 0:
				x = 1
			elif j == n - 1:
				x = -1
			j = min(n - 1, j + x)
			i += 1
		return ''.join(s)


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		d = 2 * (n - 1)
		k = len(Str)
		ans = ''
		for i in range(0, k, d):
			ans += Str[i]
		for i in range(1, n - 1):
			for j in range(i, k, d):
				ans += Str[j]
				if j + d - 2 * i < k:
					ans += Str[j + d - 2 * i]
		for i in range(n - 1, k, d):
			ans += Str[i]
		return ans


class Solution:

	def convert(self, s, n):
		a = []
		for i in range(n):
			a.append(i)
		a += a[1:len(a) - 1][::-1]
		if len(s) < len(a):
			g = a[0:len(s)]
			k = list(zip(a, s))
			ans = ''
			for i in range(n):
				for j in k:
					if j[0] == i:
						ans += j[1]
			return ans
		d = len(s) // len(a)
		r = len(s) % len(a)
		c = a * d
		c += a[0:r]
		k = list(zip(c, s))
		ans = ''
		for i in range(n):
			for j in k:
				if j[0] == i:
					ans += j[1]
		return ans


class Solution:

	def convert(self, s, n):
		if n == 1:
			return s
		res = ''
		for i in range(n):
			inc = 2 * (n - 1)
			for j in range(i, len(s), inc):
				res += s[j]
				if i > 0 and i < n - 1 and (j + inc - 2 * i < len(s)):
					res += s[j + inc - 2 * i]
		return res


class Solution:

	def convert(self, Str, n):
		res = [''] * n
		row = 0
		direction = 1
		l = len(Str)
		for j in Str:
			res[row] = res[row] + j
			if row < n - 1 and direction == 1:
				row = row + 1
			elif row > 0 and direction == -1:
				row = row - 1
			else:
				direction = direction * -1
				row = row + direction
		ans = ''
		for i in res:
			ans = ans + i
		return ans


from collections import deque

class Solution:

	def convert(self, st, n):
		if n <= 1:
			return st
		dsq = {i: '' for i in range(n)}
		dr = 1
		ct = 0
		for i in st:
			if dr == 1:
				if ct <= n - 1:
					dsq[ct] = dsq[ct] + i
				ct = ct + 1
				if ct == n:
					dr = -1
					ct = ct - 2
			else:
				if ct >= 0:
					dsq[ct] = dsq[ct] + i
				ct = ct - 1
				if ct == -1:
					dr = 1
					ct = ct + 2
		rslt = ''
		for i in range(n):
			rslt = rslt + dsq[i]
		return rslt


class Solution:

	def convert(self, Str, n):
		s = Str
		if n <= 1:
			return s
		result = ''
		for rowNum in range(n):
			i = rowNum
			up = True
			while i < len(s):
				result += s[i]
				if rowNum == 0 or rowNum == n - 1:
					i += 2 * n - 2
				else:
					if up:
						i += 2 * (n - rowNum) - 2
					else:
						i += rowNum * 2
					up ^= True
		return result


class Solution:

	def convert(self, Str, n):
		l = []
		j = 0
		k = 2 * n - 2
		if n == 1:
			k = 1
		for i in range(0, n):
			l1 = []
			l.append(l1)
		for i in range(0, len(Str), k):
			for j in range(0, n):
				l[j].append(Str[i])
				i = i + 1
				if i == len(Str):
					break
			for j in range(n - 2, 0, -1):
				if i == len(Str):
					break
				l[j].append(Str[i])
				i = i + 1
		s = ''
		for i in l:
			for j in i:
				s = s + j
		return s


class Solution:

	def convert(self, Str, n):
		if n == 1 or n == len(Str):
			return Str
		l = [''] * n
		row = 0
		mod = 1
		for i in Str:
			l[row] = l[row] + i
			if row == 0:
				mod = 1
			if row == n - 1:
				mod = -1
			row = row + mod
		s = ''
		for i in l:
			s += i
		return s


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		row = 0
		dir = 1
		res = [''] * n
		for i in Str:
			res[row] += i
			if row < n - 1 and dir == 1:
				row += 1
			elif row > 0 and dir == -1:
				row -= 1
			else:
				dir *= -1
				row += dir
		return ''.join(res)


class Solution:

	def convert(self, Str, n):
		ls = len(Str)
		out = ['' for i in range(ls)]
		ct = 0
		if n == 1:
			return Str
		flag = True
		for i in range(ls):
			out[ct] += Str[i]
			if ct == n - 1:
				flag = False
			if ct == 0:
				flag = True
			if flag:
				ct += 1
			else:
				ct -= 1
		return ''.join(out)


class Solution:

	def convert(self, Str, n):
		h = len(Str)
		t = ''
		l = []
		for i in range(n):
			l.append(t)
		i = 0
		while True:
			for j in range(n):
				l[j] += Str[i]
				i += 1
				if i == h:
					break
			if i == h:
				break
			for j in range(n - 2, 0, -1):
				l[j] += Str[i]
				i += 1
				if i == h:
					break
			if i == h:
				break
		return ''.join(l)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		n = int(input())
		solObj = Solution()
		print(solObj.convert(Str, n))


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		ans = [''] * n
		(row, switch) = (0, 1)
		for ch in Str:
			(ans[row], row) = (ans[row] + ch, row + switch)
			if row == 0 or row == n - 1:
				switch = -switch
		return ''.join(ans)


class Solution:

	def convert(self, Str, n):
		r = ['' for _ in range(n)]
		c = 0
		down = True
		for i in Str:
			r[c] += i
			if down:
				c += 1
				if c > n - 1:
					c -= 2
					down = False
			else:
				c -= 1
				if c < 0:
					c += 2
					down = True
		return ''.join(r)


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		inputs = []
		for i in range(n):
			inputs.append([])
		counter = 0
		right = True
		for i in range(len(Str)):
			inputs[counter].append(Str[i])
			if counter == n - 1:
				right = False
			elif counter == 0:
				right = True
			if right == True:
				counter += 1
			else:
				counter -= 1
		ans = ''
		for i in range(len(inputs)):
			ans += ''.join(inputs[i])
		return ans


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		m = len(Str)
		d = dict()
		for i in range(1, n + 1):
			d.update({i: ''})
		i = 0
		count = 1
		while i < m:
			while i < m and count <= n:
				d[count] += Str[i]
				i += 1
				count += 1
			count -= 2
			while i < m and count >= 1:
				d[count] += Str[i]
				i += 1
				count -= 1
			count += 2
		ans = ''
		for i in range(1, n + 1):
			ans += d[i]
		return ans


class Solution:

	def convert(self, s, row):
		(ans, idx, flag, count, startIdx, n) = ('', 0, 0, 2, 0, len(s))
		if row == 1 or row >= n:
			return s
		for i in range(n):
			if startIdx == 0 or startIdx == row - 1:
				ans += s[idx]
				idx += row + (row - 2)
				if i == n - 1:
					break
				if idx >= n or idx <= 0:
					startIdx += 1
					idx = startIdx
			else:
				if flag == 0:
					ans += s[idx]
					idx += row + (row - 2) - count
					flag = 1
				else:
					ans += s[idx]
					idx += count
					flag = 0
				if idx >= n:
					startIdx += 1
					idx = startIdx
					count += 2
					flag = 0
		return ans


class Solution:

	def convert(self, s, n):
		if n == 1:
			return s
		rows = ['' for _ in range(n)]
		l = len(s)
		direction = +1
		row = 0
		for i in range(l):
			rows[row] += str(s[i])
			if row == 0:
				direction = 1
			elif row == n - 1:
				direction = -1
			row += direction
		res = ''
		for r in range(n):
			res = res + rows[r]
		return res


class Solution:

	def convert(self, string, k):
		l = []
		n = len(string)
		if k == 0:
			return ''
		if k == 1:
			return string
		for i in range(0, n, 2 * (k - 1)):
			l.append(string[i])
		for j in range(k - 1, 1, -1):
			(i, flag) = (k - j, True)
			while i < n:
				l.append(string[i])
				if flag:
					i = i + 2 * (j - 1)
				else:
					i = i + 2 * (k - j)
				flag = not flag
		for i in range(k - 1, n, 2 * (k - 1)):
			l.append(string[i])
		return ''.join(l)


class Solution:

	def convert(self, s, k):
		l = []
		if k == 0:
			return ''
		if k == 1:
			return s
		for i in range(0, len(s), (k - 1) * 2):
			l.append(s[i])
		for j in range(1, k - 1):
			down = True
			i = j
			while i < len(s):
				l.append(s[i])
				if down:
					i += (k - j - 1) * 2
				else:
					i += (k - 1) * 2 - (k - j - 1) * 2
				down = not down
		for i in range(k - 1, len(s), (k - 1) * 2):
			l.append(s[i])
		return ''.join(l)


class Solution:

	def convert(self, Str, n):
		r = 0
		d = 1
		o = [''] * n
		for i in Str:
			o[r] = o[r] + i
			if r < n - 1 and d == 1:
				r += 1
			elif r > 0 and d == -1:
				r -= 1
			else:
				d *= -1
				r += d
		return ''.join(o)


import math

class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		ans = ['' for k in range(n)]
		curpos = 0
		mod = 1
		for i in Str:
			ans[curpos] += i
			if curpos == 0:
				mod = 1
			elif curpos == n - 1:
				mod = -1
			curpos += mod
		Str = ''
		for j in ans:
			Str += j
		return Str


class Solution:

	def convert(self, Str, n):
		l = len(Str)
		res = ''
		lis = ['' for i in range(n)]
		row = 0
		if n == 1:
			return Str
		else:
			for i in range(l):
				lis[row] += Str[i]
				if row == n - 1:
					flag = 1
				elif row == 0:
					flag = 0
				if flag == 1:
					row -= 1
				else:
					row += 1
		for i in lis:
			res += i
		return res


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		res = [''] * n
		direction = 'left'
		i = 0
		for x in Str:
			res[i] += x
			if direction == 'left':
				i += 1
				if i == n:
					direction = 'right'
					i -= 1
			if direction == 'right':
				i -= 1
				if i < 0:
					i = 1
					direction = 'left'
		return ''.join(res)


class Solution:

	def convert(self, Str, n):
		a = ['' for i in range(n)]
		if n == 1:
			return Str
		modi = 1
		currRow = 0
		for i in range(len(Str)):
			a[currRow] += Str[i]
			if currRow == 0:
				modi = 1
			if currRow == n - 1:
				modi = -1
			currRow += modi
		ans = ''
		for i in a:
			ans += i
		return ans


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		d = dict()
		for i in range(n):
			d[i] = list()
		k = 0
		l = len(Str)
		down = True
		for i in range(l):
			d[k].append(Str[i])
			if down:
				k = k + 1
			else:
				k = k - 1
			if k == n - 1:
				down = False
			elif k == 0:
				down = True
		res = ''
		for i in range(n):
			for j in d[i]:
				res += j
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		n = int(input())
		solObj = Solution()
		print(solObj.convert(Str, n))


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		i = 0
		a = 1
		res = ['' for i in range(n)]
		for k in Str:
			res[i] += k
			if i == n - 1:
				a = -1
			if i == 0:
				a = 1
			i += a
		ans = ''
		for i in res:
			ans += i
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		n = int(input())
		solObj = Solution()
		print(solObj.convert(Str, n))


class Solution:

	def convert(self, Str, n):
		l = len(Str)
		res = ''
		lis = ['' for i in range(n)]
		row = 0
		if n == 1:
			return Str
		else:
			for i in range(l):
				lis[row] += Str[i]
				if row == n - 1:
					flag = 1
				elif row == 0:
					flag = 0
				if flag == 1:
					row -= 1
				else:
					row += 1
		for i in lis:
			res += i
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		n = int(input())
		solObj = Solution()
		print(solObj.convert(Str, n))


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		m = [[] for i in range(n)]
		(c, t) = (0, 1)
		for x in Str:
			m[c].append(x)
			if c == n - 1:
				t = -1
			if c == 0:
				t = 1
			c += t
		ans = ''
		for x in m:
			ans += ''.join(x)
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		Str = input()
		n = int(input())
		solObj = Solution()
		print(solObj.convert(Str, n))


class Solution:

	def convert(self, Str, n):
		result = {}
		flag = True
		count = 0
		for (i, e) in enumerate(Str):
			result[count] = result.get(count, '') + e
			if flag:
				count += 1
				if count == n - 1:
					flag = False
			else:
				count -= 1
				if count == 0:
					flag = True
		return ''.join(result.values())


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		x = ['' for i in range(n)]
		j = 0
		down = 0
		m = True
		for i in Str:
			x[j] += i
			if j == 0:
				m = True
			elif j == n - 1:
				m = False
			if m:
				j += 1
			else:
				j -= 1
		return ''.join(x)


class Solution:

	def convert(self, Str, n):
		str = Str
		if n == 1:
			return str
		ans = ''
		flag = ''
		cnt = 0
		v = [''] * n
		for i in range(len(Str)):
			v[cnt] += str[i]
			if cnt == n - 1:
				flag = 'up'
			if cnt == 0:
				flag = 'down'
			if flag == 'up':
				cnt -= 1
			else:
				cnt += 1
		return ''.join(v)


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		l = [''] * n
		j = 0
		c = 1
		for i in range(len(Str)):
			l[j] += Str[i]
			j += c
			if j == 0 or j == n - 1:
				c *= -1
		return ''.join(l)


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		ans = [''] * len(Str)
		row = 0
		for i in range(len(Str)):
			ans[row] += Str[i]
			if row == n - 1:
				down = False
			elif row == 0:
				down = True
			if down:
				row += 1
			else:
				row -= 1
		s = ''
		for i in ans:
			s += i
		return s


class Solution:

	def convert(self, s, numRows):
		if numRows == 1 or numRows >= len(s):
			return s
		res = ['' for _ in range(numRows)]
		ind = 0
		flag = 1
		for char in s:
			res[ind] += char
			if ind == 0:
				flag = 1
			if ind == numRows - 1:
				flag = -1
			ind += flag
		return ''.join(res)


class Solution:

	def convert(self, Str, n):
		l = [''] * n
		if n == 1:
			return Str
		index = 0
		step = 1
		for i in range(len(Str)):
			l[index] += Str[i]
			if index == 0:
				step = 1
			elif index == n - 1:
				step = -1
			index += step
		return ''.join(l)


class Solution:

	def convert(self, Str, n):
		row = 0
		dire = 1
		out = [''] * n
		for i in Str:
			out[row] = out[row] + i
			if row < n - 1 and dire == 1:
				row += 1
			elif row > 0 and dire == -1:
				row -= 1
			else:
				dire *= -1
				row += dire
		return ''.join(out)


class Solution:

	def convert(self, s, n):
		if n == 1:
			return s
		l = len(s)
		increment = 2 * (n - 1)
		result = []
		for i in range(n):
			for j in range(i, l, increment):
				result.append(s[j])
				if i > 0 and i < n - 1 and (j + increment - 2 * i < l):
					result.append(s[j + increment - 2 * i])
		return ''.join(result)


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		A = [''] * n
		down = True
		row = 0
		for i in Str:
			if row < n - 1 and down:
				A[row] += i
				row += 1
			elif row == n - 1 and down:
				A[row] += i
				row -= 1
				down = False
			elif not down and row == 0:
				A[row] += i
				row += 1
				down = True
			elif not down and row < n - 1:
				A[row] += i
				row -= 1
		result = ''
		for s in A:
			result += s
		return result


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		m = len(Str)
		Str = list(Str)
		a = []
		for i in range(n):
			a.append([''] * m)
		(j, c) = (0, 1)
		for i in range(m):
			a[j][i] = Str[i]
			j += c
			if j == n - 1:
				c = -c
			if j == 0:
				c = -c
		ans = ''
		for i in a:
			ans += ''.join(i)
		return ans


import collections

class Solution:

	def convert(self, Str, n):
		s = Str
		if n == 1:
			return s
		else:
			d = collections.defaultdict(lambda : [])
			x = 0
			tba = 1
			for i in range(0, len(s)):
				d[x].append(s[i])
				x += tba
				if x == n:
					x -= 2
					tba = -1
				elif x == -1:
					x = 1
					tba = 1
			ans = []
			for i in range(0, n):
				ans += d[i]
			return ''.join(ans)


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		ls = [[] for i in range(n)]
		j = 0
		flag = False
		for i in range(len(Str)):
			ls[j].append(Str[i])
			if flag == False:
				j += 1
			else:
				j -= 1
			if j == n - 1:
				flag = True
			elif j == 0:
				flag = False
		s = ''
		for i in ls:
			d = ''.join(i)
			s = s + d
		return s


class Solution:

	def convert(self, s, n):
		if n == 1 or len(s) == n:
			return s
		l = [''] * n
		(index, step) = (0, 1)
		for i in s:
			l[index] += i
			if index == 0:
				step = 1
			elif index == n - 1:
				step = -1
			index += step
		return ''.join(l)


class Solution:

	def convert(self, Str, n):
		length = len(Str)
		i = 0
		arr = [[] for _ in range(n)]
		while i < length:
			for j in range(0, n):
				arr[j].append(Str[i])
				i += 1
				if i >= length:
					break
			if i >= length:
				break
			for k in range(j - 1, 0, -1):
				arr[k].append(Str[i])
				i += 1
				if i >= length:
					break
		result = ''
		for string in arr:
			result += ''.join(''.join(map(str, string)))
		return result


class Solution:

	def convert(self, Str, n):
		string = Str
		newStr = str()
		lent = len(Str)
		if n == 1:
			return Str
		lists = list()
		for i in range(0, n):
			lists.append(list())
		check = 0
		sign = 0
		for i in range(0, lent):
			if check == n - 1:
				sign = 1
			elif check == 0:
				sign = 0
			lists[check].append(string[i])
			if sign == 0:
				check = check + 1
			elif sign == 1:
				check = check - 1
		str2 = str()
		for i in lists:
			for j in i:
				str2 = str2 + j
		return str2


class Solution:

	def convert(self, str, k):
		if k == 1:
			return str
		arr = ['' for i in range(k)]
		length = len(str)
		row = 0
		for i in range(length):
			arr[row] += str[i]
			if row == 0:
				down = True
			if row == k - 1:
				down = False
			if down == True:
				row += 1
			else:
				row -= 1
		return ''.join(arr)


class Solution:

	def convert(self, s, n):
		if n == 1:
			return s
		ans = ''
		flag = ''
		cnt = 0
		v = [''] * n
		for i in range(len(s)):
			v[cnt] += s[i]
			if cnt == n - 1:
				flag = 'upside_movement'
			if cnt == 0:
				flag = 'downside_movement'
			if flag == 'upside_movement':
				cnt -= 1
			else:
				cnt += 1
		return ''.join(v)


class Solution:

	def convert(self, s, n):
		if n == 1:
			return s
		ans = ''
		flag = ''
		count = 0
		v = [''] * n
		for i in range(len(s)):
			v[count] += s[i]
			if count == n - 1:
				flag = 'up'
			if count == 0:
				flag = 'down'
			if flag == 'up':
				count -= 1
			if flag == 'down':
				count += 1
		return ''.join(v)


class Solution:

	def convert(self, Str, n):
		dic = [[''] * len(Str) for i in range(n)]
		r = 0
		c = 0
		up = False
		down = True
		for i in Str:
			dic[r][c] = i
			if up:
				r -= 1
				if r < 0:
					r = 0
					up = False
					down = True
			if down:
				r += 1
				if r == n:
					r -= 2
					down = False
					up = True
			c += 1
		return ''.join((''.join(i) for i in dic))


class Solution:

	def convert(self, Str, n):
		l = len(Str)
		if n == 1 or n >= l:
			return Str
		arr = ['' for i in range(n)]
		row = 0
		add = 1
		for i in range(l):
			arr[row] += Str[i]
			row += add
			if row == 0:
				add = 1
			if row == n - 1:
				add = -1
		res = ''
		for i in arr:
			res += i
		return res


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		(ans, i) = ([], 0)
		while i <= n - 1:
			(j, down) = (i, 1)
			while j < len(Str):
				ans.append(Str[j])
				if i == n - 1:
					j += 2 * n - 2
				elif i == 0 or down:
					j += 2 * (n - i) - 2
				else:
					j += 2 * (i + 1) - 2
				down = (down + 1) % 2
			i += 1
		return ''.join(ans)


class Solution:

	def convert(self, Str, n):
		row = 0
		dir = 1
		output = [''] * n
		for c in Str:
			output[row] += c
			if row < n - 1 and dir == 1:
				row += 1
			elif row > 0 and dir == -1:
				row -= 1
			else:
				dir *= -1
				row += dir
		return ''.join(output)


class Solution:

	def convert(self, Str, n):
		if n == 1 or n > len(Str):
			return Str
		lst = ['' for i in range(n)]
		cntr = 0
		for i in range(0, len(Str)):
			lst[cntr] += Str[i]
			if cntr == 0:
				down = 1
			if cntr == n - 1:
				down = 0
			if down:
				cntr += 1
			else:
				cntr -= 1
		x = ''
		for i in range(n):
			x += lst[i]
		return x


class Solution:

	def convert(self, str, n):
		if n == 1:
			return str
		a = [[] for _ in range(n)]
		m = n * 2 - 2
		for (i, c) in enumerate(str):
			if i % m < n:
				a[i % m].append(c)
			else:
				a[m - i % m].append(c)
		return ''.join([''.join(x) for x in a])


class Solution:

	def convert(self, Str, n):
		if len(Str) == 1 or n == 1:
			return Str
		len_str = len(Str)
		arr = ['' for x in range(len_str)]
		row = 0
		for i in range(len_str):
			arr[row] += Str[i]
			if row == n - 1:
				down = False
			elif row == 0:
				down = True
			if down:
				row = row + 1
			else:
				row = row - 1
		new_str = ''
		for i in range(n):
			new_str += arr[i]
		return new_str


class Solution:

	def convert(self, Str, n):
		if n == 1:
			return Str
		zig_zag = {}
		for i in range(n):
			zig_zag[i] = []
		i = 0
		control = 'zig'
		key = 0
		while i < len(Str):
			try:
				zig_zag[key].append(Str[i])
			except Exception as e:
				print(key)
				print(e)
			if control == 'zig':
				key += 1
				if key == n:
					control = 'zag'
					key -= 2
			else:
				key -= 1
				if key < 0:
					control = 'zig'
					key += 2
			i += 1
		re_str = ''
		for key in zig_zag.keys():
			re_str += ''.join(zig_zag[key])
		return re_str