Center Align Text

Version: Phuoc Hung OJ Extended

Problem Statement

Given string $s$ and a minimum field width $w$, center $s$ by inserting spaces on both sides if $|s|<w$. The total number of added spaces is $w-|s|$. Split them evenly when possible; if the number is odd, the right side receives the extra space.

If $|s|\ge w$, preserve $s$ unchanged. Put a | character at each end to make padding visible.

Input

The first line contains $s$, which may be empty. The second line contains integer $w$.

Output

Print one line in the format |centered_field|. Do not truncate or modify $s$.

Subtasks

• Subtask 1 (100 points): $0\le |s|\le40$ Unicode characters; $0\le w\le60$.

Examples

Example 1

Input

AB
6

Output

|  AB  |

Explanation. AB has length $2$, leaving four positions in width $6$; add two spaces on each side.

Example 2

Input

A
4

Output

| A  |

Explanation. A has length $1$, leaving three positions; add one space left and two right.

Example 3

Input

Xin
2

Output

|Xin|

Explanation. Xin has length $3$, exceeding width $2$, so it stays unchanged.