Zigzag Conversion

Write the characters of s in a zigzag pattern over rows rows: go down the rows one character at a time, then back up diagonally, and repeat. Then read the result row by row, left to right, top to bottom.

For s = "PAYPALISHIRING" and rows = 3:

P   A   H   N
A P L S I I G
Y   I   R

which reads "PAHNAPLSIIGYIR". With one row the string is unchanged.

Examples

Example 1

Input:

zigzag_conversion('PAYPALISHIRING', 3)

Output:

'PAHNAPLSIIGYIR'

The three rows read PAHN, APLSIIG, YIR.

Example 2

Input:

zigzag_conversion('PAYPALISHIRING', 4)

Output:

'PINALSIGYAHRPI'

The four rows read PIN, ALSIG, YAHR, PI.

Constraints

• 0 <= len(s) <= 3 * 10**5
• 1 <= rows <= 1000