F. Надо тренироваться
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
lianhua - CITRUS!
⠀

Вы — искатель приключений, работающий на футуристическую корпорацию RoboCorp. Ваш текущий уровень навыков — это целое число $$$s$$$ в диапазоне $$$[1, n]$$$, но вы не знаете его точное значение. Ваша цель — достичь уровня навыков $$$\geq n$$$, выполняя миссии для RoboCorp, но каждая миссия стоит драгоценных робокоинов.

Вы можете выбирать миссии любой сложности и любой положительной продолжительности (в часах). Однако стоимость зависит как от длины новой миссии, так и от того, как сложность новой миссии соотносится с вашей последней.

Пусть $$$x$$$ — это сложность вашей последней миссии. Если вы хотите взять новую миссию со сложностью $$$y$$$ и продолжительностью $$$l$$$:

  • Если это ваша первая миссия, или $$$y \leq x$$$, стоимость составляет $$$l$$$ робокоинов.
  • Если $$$y \gt x$$$, стоимость составляет $$$1000 + l$$$ робокоинов.

Ваши навыки улучшаются только тогда, когда вы берете миссию, сложность которой точно соответствует вашему текущему уровню навыков:

  • Если $$$y = s$$$, то ваш уровень навыков увеличивается на $$$l$$$.
  • В противном случае ваш уровень навыков не меняется.

После каждой миссии вы все равно не знаете свое фактическое значение навыков.

Вы начинаете с $$$10^6$$$ робокоинов. Найдите стратегию (последовательность миссий), которая не превышает ваш бюджет и гарантирует, что ваш уровень навыков станет как минимум $$$n$$$, независимо от того, каким был ваш начальный уровень навыков.

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

Входные данные содержит одну строку с целым числом $$$n$$$ ($$$n = 4$$$ или $$$n = 250\,000$$$) — целевой уровень навыков (то есть к концу ваш уровень навыков должен быть $$$\geq n$$$).

В этой задаче ровно $$$2$$$ теста (включая пример). В примере $$$n = 4$$$, а в другом тесте $$$n = 250\,000$$$.

Взломы в этой задаче не допускаются.

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

В первой строке выведите одно целое число $$$k$$$ ($$$0 \leq k \leq 10^6$$$) — количество миссий, которые вы планируете выполнить.

Затем выведите $$$k$$$ строк. В $$$i$$$-й строке должны содержаться два целых числа $$$y$$$ и $$$l$$$ ($$$1 \leq y, l \leq 10^6$$$) — сложность и продолжительность (в часах) $$$i$$$-й миссии соответственно.

Пример
Входные данные
4
Выходные данные
4
1 4
3 1
2 1
3 1
Примечание

В примере ваш целевой уровень навыков $$$n = 4$$$. Вы можете использовать следующую стратегию:

  • Возьмите миссию со сложностью $$$y = 1$$$ и продолжительностью $$$l = 4$$$. Это ваша первая миссия, поэтому вы платите $$$l = 4$$$ робокоинов.
  • Возьмите миссию со сложностью $$$y = 3$$$ и продолжительностью $$$l = 1$$$. Предыдущая миссия имела сложность $$$x = 1$$$, поэтому, поскольку $$$y \gt x$$$, вы платите $$$l + 1000 = 1001$$$ робокоинов.
  • Возьмите миссию со сложностью $$$y = 2$$$ и продолжительностью $$$l = 1$$$. Теперь $$$x = 3$$$, и поскольку $$$y \leq x$$$, вы платите $$$l = 1$$$ робокоин.
  • Возьмите миссию со сложностью $$$y = 3$$$ и продолжительностью $$$l = 1$$$. Теперь $$$x = 2$$$, и поскольку $$$y \gt x$$$, вы платите $$$l + 1000 = 1001$$$ робокоинов.

В общей сложности вы тратите $$$2007$$$ робокоинов, что укладывается в ваш бюджет в $$$10^6$$$ робокоинов.

Теперь мы проверим, что эта стратегия всегда работает:

  • Если ваш начальный уровень навыков был $$$1$$$, после первой миссии он станет $$$5$$$.
  • Если ваш начальный уровень навыков был $$$2$$$, после третьей миссии он станет $$$3$$$, а после четвертой миссии он станет $$$4$$$.
  • Если ваш начальный уровень навыков был $$$3$$$, после второй миссии он станет $$$4$$$.
  • Если ваш начальный уровень навыков был $$$4$$$, он останется $$$4$$$.

Таким образом, независимо от того, каким был ваш начальный уровень навыков, вы заканчиваете с уровнем навыков $$$\geq n$$$.