시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 109 20 9 11.111%

문제

인터넷프로그래밍 교수 이다솜은 XML이야말로 세상을 바꿀 혁신적인 언어라고 믿으며, 항상 학생들에게 XML의 장점을 어필한다. 그러나 잘못 사용되었다가는 지구를 파괴할 수도 있는 무시무시한 부작용도 존재하기에, 문법이 맞게 되었는지를 판정하는 파서가 필요하게 되었다. 그러나 이다솜은 XML을 할 줄 모르기에 여러분이 판독기를 구현해야 한다.

우리가 XML 문서의 형식이 유효한지 판별하는 기준은 다음과 같다.

  1. 평문---32~127 사이에 있는(32, 127도 포함) ASCII코드값으로 이루어지며, 다음 문자는 포함되면 안 된다: <, >, &
  2. 다음과 같은 문자열:
    • &lt;
    • &gt;
    • &amp;
  3. 이것들은 각각 <, >, &를 인코딩한다.
  4. &xHEX; HEX는 양의 짝수 자릿수의 16진수여야 하며, 0~9 또는 알파벳 A~F 대소문자로 이루어진다.
  5. <tag> 여는 태그이다. 태그는 숫자 또는 알파벳 소문자로 이루어진 문자열이어야 한다. 이 태그는 context 스택에 push된다.
  6. <tag/> 이 태그는 context 스택에 push되지 않는다.
  7. </tag> 닫는 태그이다. context 스택의 맨 위에 있는 태그를 pop하게 된다. 단, 이때 맨 위에 있는 태그와 이 태그의 문자열이 일치해야 한다.

문서 전체가 파싱된 후에는 context 스택은 비어 있어야 한다. 또한, 빈 문자열 역시 유효하다고 판정한다.

입력

여러 줄의 입력이 주어진다. 각 줄에 대해 유효한 XML 문법인지를 판별한다. 비어 있는 줄이 들어올 수도 있다. 입력은 파일 끝에서 종료된다.

출력

각 줄에 대하여, 해당 줄이 유효한 XML 문법을 가지고 있다면 valid를, 그렇지 않다면 invalid를 출력한다.

예제 입력 1

the quick brown fox.
the <i><b>quick</b> brown</i> fox.
<doc>fox &amp; socks.</doc>
3x+5&gt;7
Null: &x00;
<doc>the quick brown fox.
the <i>quick <b>brown</i></b> fox
fox & socks.
3x+5>7
Null: &x0;

예제 출력 1

valid
valid
valid
valid
valid
invalid
invalid
invalid
invalid
invalid
W3sicHJvYmxlbV9pZCI6IjQ4MjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJYTUwiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzc3OFx1ZDEzMFx1YjEzN1x1ZDUwNFx1Yjg1Y1x1YWRmOFx1Yjc5OFx1YmMwZCBcdWFkNTBcdWMyMTggXHVjNzc0XHViMmU0XHVjMTljXHVjNzQwIFhNTFx1Yzc3NFx1YzU3Y1x1YjlkMFx1Yjg1YyBcdWMxMzhcdWMwYzFcdWM3NDQgXHViYzE0XHVhZmMwIFx1ZDYwMVx1YzJlMFx1YzgwMVx1Yzc3OCBcdWM1YjhcdWM1YjRcdWI3N2NcdWFjZTAgXHViYmZmXHVjNzNjXHViYTcwLCBcdWQ1NmRcdWMwYzEgXHVkNTU5XHVjMGRkXHViNGU0XHVjNWQwXHVhYzhjIFhNTFx1Yzc1OCBcdWM3YTVcdWM4MTBcdWM3NDQgXHVjNWI0XHVkNTQ0XHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIwOTggXHVjNzk4XHViYWJiIFx1YzBhY1x1YzZhOVx1YjQxOFx1YzVjOFx1YjJlNFx1YWMwMFx1YjI5NCBcdWM5YzBcdWFkNmNcdWI5N2MgXHVkMzBjXHVhZDM0XHVkNTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyOTQgXHViYjM0XHVjMmRjXHViYjM0XHVjMmRjXHVkNTVjIFx1YmQ4MFx1Yzc5MVx1YzZhOVx1YjNjNCBcdWM4NzRcdWM3YWNcdWQ1NThcdWFlMzBcdWM1ZDAsIFx1YmIzOFx1YmM5NVx1Yzc3NCBcdWI5ZGVcdWFjOGMgXHViNDE4XHVjNWM4XHViMjk0XHVjOWMwXHViOTdjIFx1ZDMxMFx1YzgxNVx1ZDU1OFx1YjI5NCBcdWQzMGNcdWMxMWNcdWFjMDAgXHVkNTQ0XHVjNjk0XHVkNTU4XHVhYzhjIFx1YjQxOFx1YzVjOFx1YjJlNC4gXHVhZGY4XHViN2VjXHViMDk4IFx1Yzc3NFx1YjJlNFx1YzE5Y1x1Yzc0MCBYTUxcdWM3NDQgXHVkNTYwIFx1YzkwNCBcdWJhYThcdWI5NzRcdWFlMzBcdWM1ZDAgXHVjNWVjXHViN2VjXHViZDg0XHVjNzc0IFx1ZDMxMFx1YjNjNVx1YWUzMFx1Yjk3YyBcdWFkNmNcdWQ2MDRcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2YjBcdWI5YWNcdWFjMDAgWE1MIFx1YmIzOFx1YzExY1x1Yzc1OCBcdWQ2MTVcdWMyZGRcdWM3NzQgXHVjNzIwXHVkNmE4XHVkNTVjXHVjOWMwIFx1ZDMxMFx1YmNjNFx1ZDU1OFx1YjI5NCBcdWFlMzBcdWM5MDBcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWQzYzlcdWJiMzgtLS0zMn4xMjcgXHVjMGFjXHVjNzc0XHVjNWQwIFx1Yzc4OFx1YjI5NCgzMiwgMTI3XHViM2M0IFx1ZDNlY1x1ZDU2OCkgQVNDSUlcdWNmNTRcdWI0ZGNcdWFjMTJcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWMwXHViYTcwLCBcdWIyZTRcdWM3NGMgXHViYjM4XHVjNzkwXHViMjk0IFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0OiAmbHQ7LCAmZ3Q7LCAmYW1wOzxcL2xpPlxyXG5cdDxsaT5cdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YmIzOFx1Yzc5MFx1YzVmNDpcclxuXHQ8dWw+XHJcblx0XHQ8bGk+JmFtcDtsdDs8XC9saT5cclxuXHRcdDxsaT4mYW1wO2d0OzxcL2xpPlxyXG5cdFx0PGxpPiZhbXA7YW1wOzxcL2xpPlxyXG5cdDxcL3VsPlxyXG5cdDxcL2xpPlxyXG5cdDxsaT5cdWM3NzRcdWFjODNcdWI0ZTRcdWM3NDAgXHVhYzAxXHVhYzAxICZsdDssICZndDssICZhbXA7XHViOTdjIFx1Yzc3OFx1Y2Y1NFx1YjUyOVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+JmFtcDt4SEVYOyBIRVhcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzlkZFx1YzIxOCBcdWM3OTBcdWI5YmZcdWMyMThcdWM3NTggMTZcdWM5YzRcdWMyMThcdWM1ZWNcdWM1N2MgXHVkNTU4XHViYTcwLCAwfjkgXHViNjEwXHViMjk0IFx1YzU0Y1x1ZDMwY1x1YmNiMyBBfkYgXHViMzAwXHVjMThjXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC48XC9saT5cclxuXHQ8bGk+Jmx0O3RhZyZndDsgXHVjNWVjXHViMjk0IFx1ZDBkY1x1YWRmOFx1Yzc3NFx1YjJlNC4gXHVkMGRjXHVhZGY4XHViMjk0IFx1YzIyYlx1Yzc5MCBcdWI2MTBcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1ZDBkY1x1YWRmOFx1YjI5NCBjb250ZXh0IFx1YzJhNFx1ZDBkZFx1YzVkMCBwdXNoXHViNDFjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT4mbHQ7dGFnXC8mZ3Q7IFx1Yzc3NCBcdWQwZGNcdWFkZjhcdWIyOTQgY29udGV4dCBcdWMyYTRcdWQwZGRcdWM1ZDAgcHVzaFx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPiZsdDtcL3RhZyZndDsgXHViMmViXHViMjk0IFx1ZDBkY1x1YWRmOFx1Yzc3NFx1YjJlNC4gY29udGV4dCBcdWMyYTRcdWQwZGRcdWM3NTggXHViOWU4IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkMGRjXHVhZGY4XHViOTdjIHBvcFx1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YjJlOCwgXHVjNzc0XHViNTRjIFx1YjllOCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1ZDBkY1x1YWRmOFx1YzY0MCBcdWM3NzQgXHVkMGRjXHVhZGY4XHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM3N2NcdWNlNThcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YmIzOFx1YzExYyBcdWM4MDRcdWNjYjRcdWFjMDAgXHVkMzBjXHVjMmYxXHViNDFjIFx1ZDZjNFx1YzVkMFx1YjI5NCBjb250ZXh0IFx1YzJhNFx1ZDBkZFx1Yzc0MCBcdWJlNDRcdWM1YjQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwXHVkNTVjLCBcdWJlNDggXHViYjM4XHVjNzkwXHVjNWY0IFx1YzVlZFx1YzJkYyBcdWM3MjBcdWQ2YThcdWQ1NThcdWIyZTRcdWFjZTAgXHVkMzEwXHVjODE1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNWVjXHViN2VjIFx1YzkwNFx1Yzc1OCBcdWM3ODVcdWI4MjVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWM3MjBcdWQ2YThcdWQ1NWMgWE1MIFx1YmIzOFx1YmM5NVx1Yzc3OFx1YzljMFx1Yjk3YyBcdWQzMTBcdWJjYzRcdWQ1NWNcdWIyZTQuIFx1YmU0NFx1YzViNCBcdWM3ODhcdWIyOTQgXHVjOTA0XHVjNzc0IFx1YjRlNFx1YzViNFx1YzYyYyBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NDAgXHVkMzBjXHVjNzdjIFx1YjA1ZFx1YzVkMFx1YzExYyBcdWM4ODVcdWI4Y2NcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1YzkwNFx1YzVkMCBcdWIzMDBcdWQ1NThcdWM1ZWMsIFx1ZDU3NFx1YjJmOSBcdWM5MDRcdWM3NzQgXHVjNzIwXHVkNmE4XHVkNTVjIFhNTCBcdWJiMzhcdWJjOTVcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNFx1YmE3NCB2YWxpZFx1Yjk3YywgXHVhZGY4XHViODA3XHVjOWMwIFx1YzU0YVx1YjJlNFx1YmE3NCBpbnZhbGlkXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0ODI4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiWE1MIiwiZGVzY3JpcHRpb24iOiI8cD5JbiB0aGlzIHByb2JsZW0sIHlvdSBhcmUgYXNrZWQgdG8gZGV0ZXJtaW5lIGlmIGEgZ2l2ZW4gZG9jdW1lbnQgc2F0aXNmaWVzIHRoZSBzeW50YXggb2YgYW4gWE1MLWxpa2UgbGFuZ3VhZ2UuPFwvcD5cclxuXHJcbjxwPkEgc2ltcGxlIFhNTC1saWtlIGRvY3VtZW50IGNhbiBiZSBwYXJzZWQgYXMgYSBzZXF1ZW5jZSBvZiB0aGUgZm9sbG93aW5nOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlBsYWluIHRleHQtLS1BU0NJSSBjb2RlcyBiZXR3ZWVuIDMyIGFuZCAxMjcgKGluY2x1c2l2ZSksIHdpdGggbm9uZSBvZiB0aGUgZm9sbG93aW5nIHN5bWJvbHM6ICZsdDssICZndDssICZhbXA7PFwvbGk+XHJcblx0PGxpPlRoZSBzZXF1ZW5jZXM6XHJcblx0PHVsPlxyXG5cdFx0PGxpPiZhbXA7bHQ7PFwvbGk+XHJcblx0XHQ8bGk+JmFtcDtndDs8XC9saT5cclxuXHRcdDxsaT4mYW1wO2FtcDs8XC9saT5cclxuXHQ8XC91bD5cclxuXHQ8XC9saT5cclxuXHQ8bGk+VGhlc2UgZW5jb2RlIGEgJmx0OywgJmd0Oywgb3IgJmFtcDsgcmVzcGVjdGl2ZWx5LjxcL2xpPlxyXG5cdDxsaT4mYW1wO3hIRVg7IEhFWCBtdXN0IGJlIGFueSBldmVuIChwb3NpdGl2ZSkgbnVtYmVyIG9mIHVwcGVyIG9yIGxvd2VyIGNhc2UgaGV4YWRlY2ltYWwgZGlnaXRzLCBhbmQgdGhpcyByZXByZXNlbnRzIHRoZSBieXRlcyBnaXZlbi48XC9saT5cclxuXHQ8bGk+Jmx0O3RhZyZndDsgVGFnIGNhbiBiZSBhbnkgbG93ZXJjYXNlIGFscGhhbnVtZXJpYyBzdHJpbmcuIFRoaXMgdGFnIGlzIHB1c2hlZCBvbnRvIHRoZSBjb250ZXh0IHN0YWNrLjxcL2xpPlxyXG5cdDxsaT4mbHQ7dGFnXC8mZ3Q7IFRoaXMgdGFnIGlzIG5vdCBwdXNoZWQgb250byB0aGUgY29udGV4dCBzdGFjayAodGhlcmUgaXMgbm8gY2xvc2luZyBjb250ZXh0KS48XC9saT5cclxuXHQ8bGk+Jmx0O1wvdGFnJmd0OyBUaGlzIHRhZyByZW1vdmVzIHRoZSAmbHQ7dGFnJmd0OyBjb250ZXh0IGZyb20gdGhlIHN0YWNrLCB3aGljaCBtdXN0IGJlIHRvcG1vc3Qgb24gdGhlIHN0YWNrLjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPkJ5IHRoZSB0aW1lIHRoZSBlbnRpcmUgZG9jdW1lbnQgaXMgcGFyc2VkLCB0aGUgY29udGV4dCBzdGFjayBpcyBlbXB0eSBmb3IgYSB2YWxpZCBkb2N1bWVudC4gV2Ugc2hvdWxkIGFsc28gbm90ZSB0aGF0IHRoZSBlbXB0eSBzdHJpbmcgaXMgY29uc2lkZXJlZCB2YWxpZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPllvdSB3aWxsIGJlIGdpdmVuIGEgbnVtYmVyIG9mIGRvY3VtZW50cyB0byBwcm9jZXNzLiBFYWNoIGRvY3VtZW50IGlzIGdpdmVuIGFzIG9uZSBsaW5lIG9mIHRleHQgd2hpY2ggbWF5IGJlIGVtcHR5LiBUaGUgaW5wdXQgaXMgdGVybWluYXRlZCBieSB0aGUgZW5kIG9mIGZpbGUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZG9jdW1lbnQgZ2l2ZW4sIHByaW50IHZhbGlkIG9uIGEgc2luZ2xlIGxpbmUgaWYgaXQgaXMgYSB2YWxpZCBYTUwtbGlrZSBkb2N1bWVudCwgb3IgaW52YWxpZCBvdGhlcndpc2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d