μ§λ©΄ μμλ μλμμλΆν° μλ‘ κ°μ λκΈ°μΈ΅μ΄ μ°¨λ‘λλ‘ μ‘΄μ¬νλ€. λ²μ§Έ λκΈ°μΈ΅μ λ°μ¬μ¨μ μ΄λ€.
μ²μμ λΉμ μ μ΄ μ§λ©΄μ λλ¬νλ€. μ§λ©΄μ μμ μκ² λλ¬ν λΉμ λͺ¨λ λ€μ μμͺ½μΌλ‘ λ°©μΆνλ€.
λΉμ΄ μλμμ μλ‘ μ΄λνλ€κ° λ²μ§Έ λκΈ°μΈ΅μ λλ¬νλ©΄, νμ¬ λΉμ μμ λ μ§λ©΄μΌλ‘ λ€μ λ°μ¬λκ³ , λλ¨Έμ§λ μμͺ½μΌλ‘ ν΅κ³Όνλ€. λͺ¨λ λκΈ°μΈ΅μ ν΅κ³Όν λΉμ μ°μ£Όλ‘ λΉ μ Έλκ° λ€μ λμμ€μ§ μλλ€. λΉμ΄ μμμ μλλ‘ μ΄λν λλ λͺ¨λ λΉμ΄ ν΅κ³Όλ¨μ μ μνλΌ.
μ§λ©΄μΌλ‘ λ°μ¬λ λΉμ λ€μ μ§λ©΄μ λλ¬νκ³ , μ§λ©΄μ κ·Έ λΉμ λ€μ μμͺ½μΌλ‘ λ°©μΆνλ€. μ΄ κ³Όμ μ 무νν λ°λ³΅λλ€.
무νν μκ°μ΄ μ§λ λ€, μ§λ©΄μ λλ¬ν λΉμ μ΄λμ ꡬνμ¬λΌ. μ²μμ μ§λ©΄μ λλ¬ν λΉμ μ λ μ΄λμ ν¬ν¨νλ€.
μ λ΅μ μ 리μκ° λ μ μμΌλ―λ‘, μ λ΅μ κΈ°μ½λΆμ λ‘ λνλμ λ μ μΆλ ₯νλ€.
λ¨, μ μ μ λν μμ¬μμμ΄λ€.
μμ¬μμμ μ μ
μ΄ λ¬Έμ μ μ λ΅μ μ μκ° μλ μ μλ€. λ°λΌμ μ λ΅μ κΈ°μ½λΆμ λ‘ λνλμ λ, λ₯Ό μΆλ ₯νλ€.
μ¬κΈ°μ μ μ μμ¬μμ, λλ λͺ¨λλ¬ μμμ΄λ€.
μ μ μ μ λν μμ¬μμλ, λ€μμ λ§μ‘±νλ μ μ λ₯Ό μλ―Ένλ€.
μ΄λ λ₯Ό μ΄λΌκ³ μ΄λ€.
μλ₯Ό λ€μ΄ μΌ λ,
μ΄λ―λ‘ μ΄λ€.
κ° μμμ΄κ³ κ° μ λ°°μκ° μλλΌλ©΄, νλ₯΄λ§μ μμ 리μ μν΄
κ° μ±λ¦½νλ€. λ°λΌμ λΉ λ₯Έ κ±°λμ κ³±μ μ΄μ©ν΄ μκ°μ μμ¬μμλ₯Ό ꡬν μ μλ€.
Input
μ λ ₯μ λ€μκ³Ό κ°μ νμμΌλ‘ μ£Όμ΄μ§λ€.
Output
무νν μκ°μ΄ μ§λ λ€ μ§λ©΄μ λλ¬ν λΉμ μ΄λμ λ‘ λλ λλ¨Έμ§ ννλ‘ μΆλ ₯νλ€.
μ λ΅μ κΈ°μ½λΆμ λ‘ λνλμ λ, μ μΆλ ₯ν΄μΌ νλ€.
Constraints
- .
- ().
- μ λ ₯μΌλ‘ μ£Όμ΄μ§λ λͺ¨λ κ°μ μ μμ΄λ€.
Subtasks
Samples
μ²μμλ λ§νΌμ λΉμ΄ μ§λ©΄μ λλ¬νλ€.
κ·Έ ν λ°©μΆλ λΉμ μΈ μ΄ λ€μ μ§λ©΄μ λλ¬νκ³ , κ·Έ λ€μμλ μ μΈ κ° λ€μ μ§λ©΄μ λλ¬νλ€.
λ°λΌμ μ΄λμ
μ΄λ€.
μ΄λ―λ‘ μ λ΅μ μ΄λ€.