์ฒด์คํ์ ํฌ๊ธฐ๋ ์ด๋ฉฐ, ์๋ก ๋ค๋ฅธ ๋ ๊ธฐ๋ฌผ์ ๊ฐ์ ์นธ์ ๋์ผ ์ ์๋ค.
๋์ดํธ๋ ํ ๋ฐฉํฅ์ผ๋ก ๋ ์นธ ์ด๋ํ ๋ค ๊ทธ ๋ฐฉํฅ๊ณผ ์์ง์ธ ๋ฐฉํฅ์ผ๋ก ํ ์นธ ์ด๋ํ๋ค. ์ด๋ ์ค ๋ค๋ฅธ ๊ธฐ๋ฌผ์ ๋ฐ์ด๋์ ์ ์๋ค.
๋น์์ ๋ค ๋๊ฐ์ ๋ฐฉํฅ ์ค ํ๋๋ก ์ํ๋ ๋งํผ ์ด๋ํ๋ค. ๋จ, ์ฒด์คํ ๋ฐ์ผ๋ก ๋๊ฐ ์ ์์ผ๋ฉฐ ์ด๋ ๊ฒฝ๋ก์ ๋ค๋ฅธ ๋น์์ด๋ ๋์ดํธ๊ฐ ์์ผ๋ฉด ๊ทธ ๊ธฐ๋ฌผ์ ๋์ด๊ฐ ์ ์๋ค.
ํน์ ์ํ์ข์ฐ ๋๋ ๋๊ฐ์ ๋ฐฉํฅ์ผ๋ก ํ ์นธ ์ด๋ํ ์ ์๋ค. ์ด๋ํ๋ ค๋ ์นธ์ ์๋ ๊ธฐ๋ฌผ์ด ์๋ค๋ฉด ๊ทธ ๊ธฐ๋ฌผ์ ์ก๊ณ ํด๋น ์นธ์ผ๋ก ์ด๋ํ ์ ์๋ค.
ํน์ด ํ์ฌ ์๋ ์นธ์ด ์๋ ๊ธฐ๋ฌผ์๊ฒ ๊ณต๊ฒฉ๋ฐ๊ณ ์์ผ๋ฉฐ, ํน์ด ์ด๋ํ ์ ์๋ ๋ชจ๋ ์นธ๋ ์์ ํ์ง ์๋ค๋ฉด ํน์ ์ฒดํฌ๋ฉ์ดํธ ์ํ์ด๋ค. ํน์ด ์๋ ๊ธฐ๋ฌผ์ด ์๋ ์นธ์ผ๋ก ์ด๋ํ๋ ๊ฒฝ์ฐ์๋ ๊ทธ ๊ธฐ๋ฌผ์ ์ก์ ์ ๊ฑฐํ ๋ค, ๋จ์ ์๋ ๊ธฐ๋ฌผ ์ค ํ๋๊ฐ ๊ทธ ์นธ์ ๊ณต๊ฒฉํ๋์ง๋ฅผ ํ๋จํ๋ค.
๋ช ์ต์ด๋ ์์ ์ ํน์ ์ฌ์ฉํ์ง ์๊ณ , ์ ํํ ๊ฐ์ ๋์ดํธ์ ๊ฐ์ ๋น์๋ง ์ฒด์คํ์ ๋ฐฐ์นํ๋ค.
ํน์ ์์น๋ฅผ ํ๋ ๊ณ ์ ํ์ ๋, ๋์ดํธ์ ๋น์์ ์ ์ ํ ๋ฐฐ์นํ์ฌ ๊ทธ ํน์ ์ฒดํฌ๋ฉ์ดํธ ์ํ๋ก ๋ง๋ค ์ ์๋ค๋ฉด ๊ทธ ์์น๋ฅผ ๊ฐ๋ฅํ ์์น๋ผ๊ณ ํ์. ๋ฐฐ์น ๋ฐฉ๋ฒ์ ์์ ๊ด๊ณ์์ด ๊ฐ ์์น๋ ํ ๋ฒ๋ง ์ผ๋ค.
๊ฐ๋ฅํ ํน์ ์์น์ ๊ฐ์๋ฅผ ๊ตฌํ์ฌ๋ผ.
Input
์ ๋ ฅ์ ๋ค์๊ณผ ๊ฐ์ ํ์์ผ๋ก ์ฃผ์ด์ง๋ค.
Output
์ฒซ์งธ ์ค์ ๊ฐ๋ฅํ ํน์ ์์น์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
Constraints
- .
- .
- .
- .
Subtasks
Samples
์กฐ๊ฑด์ ๋ง์กฑํ๋ ํน์ ์์น๋ ๊ฐ์ด๋ค.
์กฐ๊ฑด์ ๋ง์กฑํ๋ ํน์ ์์น๋ ๊ฐ์ด๋ค.