Известный шеф-повар опять приготовил \(n\) блюд: \(i\)-е блюдо состоит из \(a_i\) грамм рыбы и \(b_i\) грамм мяса.
Организаторы банкета считают два блюда \(i\) и \(j\) равными, если \(a_i=a_j\) и одновременно \(b_i=b_j\).
Организаторы банкета оценивают разнообразие \(n\) блюд следующим образом. Разнообразие набора блюд равно количеству различных блюд в нём. Чем разнообразие меньше, тем лучше.
Для того, чтобы уменьшить разнообразие, был приглашен дегустатор. Он съест ровно \(m_i\) грамм еды из каждого блюда. Для каждого блюда дегустатор определяет отдельно сколько он съест рыбы, а сколько мяса. Главное, чтобы суммарно в \(i\)-м блюде он съел ровно \(m_i\) грамм.
Определите, сколько какого типа еды должен съесть дегустатор в каждом из блюд, чтобы величина разнообразия оказалась минимально возможной. Если ответов несколько, выведите любой из них.
Выходные данные
Для каждого набора входных данных выведите в первой строке минимальное значение разнообразия, которое можно достичь, съев из блюда \(i\) ровно \(m_i\) грамм еды (для всех \(i\) от \(1\) до \(n\)).
Далее выведите \(n\) строк, которые описывают способ это сделать: \(i\)-я строка должна содержать два целых числа \(x_i\) и \(y_i\) (\(0 \leq x_i \leq a_i\); \(0 \leq y_i \leq b_i\); \(x_i+y_i=m_i\)), где \(x_i\) — сколько грамм рыбы надо съесть из \(i\)-го блюда, а \(y_i\) — сколько грамм мяса.
Если есть несколько способов добиться минимального баланса, выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
10 10 2
9 9 0
10 9 1
2
3 4 1
5 1 2
3
7 2 5
6 5 4
5 5 6
1
13 42 50
5
5 7 12
3 1 4
7 3 7
0 0 0
4 1 5
|
1
1 1
0 0
1 0
2
0 1
1 1
2
3 2
0 4
1 5
1
8 42
2
5 7
3 1
4 3
0 0
4 1
|