Replace the Characters

Given a string $S$ of length $N$ consisting of lowercase English letters, let $S_i$ denote the $i$-th character of $S$. The characters of $S$ are numbered from $0$ to $N − 1$.

You are allowed to modify the string using the following operation:

• Change one character to another. More formally, choose an integer $i \ (0 ≤ i ≤ N − 1)$ and a lowercase English letter $c$, and set $S_i$ to $c$.

Write a program that determines the minimum number of operations needed to transform $S$ into a string that has its characters sorted in non-decreasing order.

Also, print a sequence of operations that achieves this goal (see the Output section below). If there are multiple answers, please output one that makes the resulting string lexicographically minimal.

Input

The first line of input contains a single integer $N$.

The second line of input contains a string $S$ of length $N$ consisting of lowercase English letters.

Output

The first line of output must contain a single integer $K$, the minimum number of operations.

Each of the following $K$ lines must contain an integer $i \ (0 ≤ i ≤ N − 1)$ and lowercase English letter $c$, separated by a space, describing an operation.

Note that if there are multiple possible answers, you must output one that makes the resulting string lexicographically minimal.

Constraints and clarifications

• $1 \leq N \leq 100 \ 000$
• $|S| = N$
• $S_i$ is a lowercase English letter for each $i = 0 \dots N − 1$.

Example 1

stdin

2
ba

stdout

1
0 a

Explanation

In the first sample case, if we replace the first character with the letter a, then the string becomes aa which is sorted in non-decreasing order.

Note that the string would also become sorted if we replace the second character with the letter b (obtaining the string bb), but it is not the lexicographically minimal solution, and therefore it is not a correct output.

Example 2

stdin

2
ab

stdout

0

Explanation

In the second sample case, the string is already sorted in non-decreasing order, and therefore no operations are needed.