Even President

In a land known for its mathematical brilliance, Nepsland, two groups of thinkers often found themselves at odds: the Odd Team and the Even Team.

The Even Team, proud of their logical rigor, made a bold claim—they said they could determine whether the number of adjacent different values (0 next to 1 or 1 next to 0) in any binary sequence was odd or even, even if some parts were hidden. The Odd Team, skeptical, decided to challenge them.

"Fine," they said. "We'll create binary strings with some characters hidden, using '?' to represent an unknown '0' or '1'. We'll then give you a set of queries—intervals in the string—and you must tell us if the number of adjacent different characters in each interval is even, odd, or impossible to determine."

You were chosen as the representative of the Even Team. Your task: build a system that analyzes these queries. For each one, if it’s possible to always determine the parity (odd or even) regardless of how the '?' are filled, you must output:

• 1 if the number is always odd
• 0 if it's always even
• -1 if it's impossible to tell

Input

• The first line contains a string $S$ of length $N$ consisting of the characters '0', '1', and '?'.