{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eAfter having a wonderful time at the Carnival test festival, Jão and his friends decided to go for an after party in his house. At some point Jão convinced them to play a classical mathematical puzzle. He put his friends in a line and gave each one of them a typical Carnival hat colored in \u003cspan class\u003d\"tex-font-style-it\"\u003eblack\u003c/span\u003e or \u003cspan class\u003d\"tex-font-style-it\"\u003ewhite\u003c/span\u003e. They were arranged in such a way that they could only see the hats of people that were in front of them. In particular, the last person could see everyone\u0027s hat and the first could see nothing.\u003c/p\u003e\u003cp\u003eThis game must be played from the last one on the line to the first. Each person should try, in this order, to guess the color of his own hat \u003cspan class\u003d\"tex-font-style-bf\"\u003eout loud\u003c/span\u003e. For that, the participants can agree on some strategy \u003cspan class\u003d\"tex-font-style-bf\"\u003ebefore\u003c/span\u003e getting the hats.\u003c/p\u003e\u003cp\u003eJão had so much fun watching his drunk friends trying to tackle the puzzle. Now he decided to teach them a powerful strategy. Let $$$n$$$ be the number of participants in the game, and let they have numbers from 1 to $$$n$$$, from the first person in line to the last. Let the black hat have an associated value of $$$1$$$ and the white one have a value of $$$0$$$. Then we can always guess at least $$$n-1$$$ values correctly by following this strategy:\u003c/p\u003e\u003col\u003e \u003cli\u003e The last one in line have no information about his own hat, so he should guess the \u003cspan class\u003d\"tex-font-style-tt\"\u003exor\u003c/span\u003e ($$$\\oplus$$$) of all the hats he can see; \u003c/li\u003e\u003cli\u003e The others players in line should do something different. Let $$$X$$$ be the \u003cspan class\u003d\"tex-font-style-tt\"\u003exor\u003c/span\u003e of the values guessed by previous players. Let $$$Y$$$ be the \u003cspan class\u003d\"tex-font-style-tt\"\u003exor\u003c/span\u003e of the hats the current player can see. If $$$X \u003d Y$$$, then his own hat must be \u003cspan class\u003d\"tex-font-style-it\"\u003ewhite\u003c/span\u003e, otherwise it must be \u003cspan class\u003d\"tex-font-style-it\"\u003eblack\u003c/span\u003e; \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eNotice that every player will follow (2), except for the last one in line, which will follow (1). This strategy ensures that the first $$$n-1$$$ participants in line will guess correctly. Can you see why it works?\u003c/p\u003e\u003cp\u003eUnfortunately, Jão\u0027s friends are drunk, so they tend to mess the strategy up. When someone messes up, that means that he should have guessed $$$x$$$ according to the strategy, but guessed $$$x \\oplus 1$$$. Your task, given the guesses of each participant in line, is to decide if there is a hat distribution such that we can say no one messed up given those guesses.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe only input line contains a binary string $$$s$$$ ($$$|s| \u003d n \\leq 10^5$$$). The $$$i$$$-th character of $$$s$$$ represents the color guessed by the $$$i$$$-th guy in the line (\u003cspan class\u003d\"tex-font-style-tt\"\u003e0\u003c/span\u003e for white, \u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e for black).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput \u003cspan class\u003d\"tex-font-style-tt\"\u003eYES\u003c/span\u003e if there is a hat distribution such that we can say no one messed up. Otherwise, output \u003cspan class\u003d\"tex-font-style-tt\"\u003eNO\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e10010\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e01110\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eNO\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}