L. ABC
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string consisting of letters 'a', 'b' and 'c', and there are 4 kinds of operations you can do on it:

  1. Replace a character 'a' in the string with "ab".
  2. Replace a character 'b' in the string with "bc".
  3. Replace a character 'c' in the string with "ba".
  4. Remove a substring(consecutive characters) "abc" from the string.

Let $$$n$$$ be the length of the string, can you remove the whole string using at most $$$3n$$$ operations or state that it's impossible to do so?

Input

The first and only line contains the string $$$s$$$($$$1 \le n \le 2\times 10^5$$$) consisting of characters 'a', 'b' and 'c'.

Output

If it's impossible to remove the whole string print -1, otherwise in the first line print $$$m$$$($$$1 \le m \le 3n$$$), the number of operations you will make.

In each of the next $$$m$$$ lines print an operation of the form $$$type_i,index_i$$$($$$1 \le type_i \le 4, 1 \le index_i \le |s|$$$), the type of the $$$i$$$th operation and the index of the character you want to do the $$$i$$$th operation on, if the operation is of type 4, then $$$index_i$$$ should be the index of the first character of the substring "abc" that you want to remove. $$$Index_i$$$ is $$$1-$$$based and the string is updated after each operation, see example notes for better understanding.

Examples
Input
acab
Output
4
1 1
4 1
2 2
4 1
Input
bac
Output
-1
Note

This is how the string changes in the first example: acab$$$\rightarrow$$$abcab$$$\rightarrow$$$ab$$$\rightarrow$$$abc$$$\rightarrow\phi$$$, where $$$\phi$$$ is the empty string.