Монокарп и Поликарп играют в компьютерную игру. В этой игре есть \(n\) боссов, пронумерованных от \(1\) до \(n\).
Они будут сражаться с каждым боссом по следующему алгоритму:
- Монокарп делает \(k\) попыток убить босса;
- Поликарп делает \(k\) попыток убить босса;
- Монокарп делает \(k\) попыток убить босса;
- Поликарп делает \(k\) попыток убить босса;
- ...
Монокарп убивает \(i\)-го босса со своей \(a_i\)-й попытки. Поликарп убивает \(i\)-го босса со своей \(b_i\)-й попытки. Когда один из них убивает \(i\)-го босса, они переходят к \((i+1)\)-му боссу. Счетчики количества попыток сбрасываются для них обоих. Когда один из них убивает \(n\)-го босса, игра заканчивается.
Найдите все такие значения \(k\) от \(1\) до \(n\), что Монокарп убивает всех боссов.
Выходные данные
На каждый набор входных данных выведите две строки. В первой строке должно быть записано одно целое число \(\mathit{cnt}\) — количество таких значений \(k\) от \(1\) до \(n\), что Монокарп убьет всех боссов в первой строке. Во второй строке выведите \(\mathit{cnt}\) различных целых чисел — сами значения \(k\).
Примечание
Рассмотрим последний набор входных данных примера.
Пусть \(k = 1\). Сначала Монокарп делает одну попытку убить первого босса. Она успешная, так как \(a_1 = 1\). Затем Монокарп делает одну попытку убить второго босса. Она неуспешная, так как \(a_2 > 1\). Тогда Поликарп делает попытку. Она также неуспешная, так как \(b_2 > 1\). Затем Монокарп делает еще попытку. Она все еще неуспешная, так как \(a_2 > 2\). Это продолжается до тех пор, пока Поликарп наконец не убьет босса со своей третьей попытки. Монокарп не убил этого босса, поэтому \(k = 1\) — это не ответ.
Пусть \(k = 2\). Монокарп все еще убивает первого босса с первой попытки. Затем делает две неуспешные попытки на второго босса. Затем Поликарп делает две неуспешные попытки. Затем Монокарп делает еще две попытки и убивает босса со своей четвертой попытки. Третий босс похож на второго. Сначала две неуспешные попытки от Монокарпа. Затем две неуспешные попытки от Поликарпа. Затем у Монокарпа есть еще две попытки, но уже его первая успешная, так как \(a_3 = 3\). Четвертый босс также убит Монокарпом. Поэтому \(k = 2\) — это ответ.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 1 1
2 3 1
1
1
1
4
1 4 3 2
3 3 4 1
|
3
1 2 3
1
1
2
2 4
|