ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

## 2058. 100500 palidnromes

Time limit: 1.0 second
Memory limit: 64 MB
For every prefix of some given string, determine whether it is possible to split it into 1, 2, 3, 4, 5, …, n non-empty palindromes. Note that if we can split a string into k palindromes then we can split it into k + 2 palindromes.

### Input

The input contains a string of n lowercase Latin letters (1 ≤ n ≤ 3 · 105).

### Output

Output 2n integers. The i-th line should contain minimal odd k (or −1 if it doesn’t exist) and minimal even k (or −2 if it doesn’t exist) such that we can split string s[1..i] into k palindromes.

inputoutput
```abaa
```
```1 -2
-1 2
1 -2
3 2
```

### Notes

abaa = aba|a = a|b|aa = a|b|a|a.
Problem Author: Mikhail Rubinchik
Problem Source: Palindromic Contest, July 11, 2015