eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Настольная игра

Настольная игра

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

Юра и Рома любят скоротать время за различными настольными играми. Недавно компания HAL выпустила новую настольную игру "Атомы". Правила её заключаются в следующем. В игровой набор входит небольшое количество атомов (около 10^100). В начале игры нужно подбросить игральный многогранник, на гранях которого записаны все натуральные числа от 1 до 2·10^9. После того, как на многограннике выпадает число N, нужно проинициализировать игровое поле: создать N кучек с атомами, в i-й кучке должно быть ровно i атомов.

Во время игры Юра и Рома ходят по очереди. За один ход можно взять любое положительное количество атомов из любой ещё не пустой кучки и убрать их из игры. Проигрывает тот, кто не может сделать следующий ход.

Юра очень любит придумывать забавные факты про игру "Атомы". Сегодня его заинтересовал вопрос: "А сколько же можно сделать различных первых ходов?". На этот вопрос Рома очень быстро смог ответить, но тут же последовал другой: "А сколько же можно сделать первых ходов так, чтобы при оптимальной игре оппонента всё равно можно было выиграть?". Второй вопрос у ребят вызвал затруднения, они бросили игру и пошли писать перебор...

Входные данные

В первой строке ввода записано одно положительное целое число N (1N2·10^9), которое выпало на кубике в начале игры.

Выходные данные

В единственной строке выведите через пробел два целых числа - ответы на первый и второй вопросы, заданные Юрой.

Пример

Входные данные #1
1
Выходные данные #1
1 1
Источник Yandex.Algorithm, Qualification, July 8-9, 2013