У Дореми есть корневое дерево размера \(n\), корнем которого является вершина \(r\). Изначально на вершине \(i\) записано число \(w_i\). Дореми может использовать свою силу, чтобы выполнить данную операцию не более \(k\) раз:
- Выберем вершину \(x\) (\(1 \leq x \leq n\)).
- Пусть \(s = \frac{1}{|T|}\sum_{i \in T} w_i\), где \(T\) — множество всех вершин в поддереве \(x\).
- Для всех \(i \in T\) присваиваем \(w_i := s\).
Дореми хочет узнать, каким будет лексикографически минимальный\(^\dagger\) массив \(w\) после выполнения всех операций. Можете ли вы ей помочь?
Если ответов несколько, вы можете вывести любой из них.
\(^\dagger\) Для массивов \(a\) и \(b\) длины \(n\), \(a\) лексикографически меньше \(b\) тогда и только тогда, когда существует индекс \(i\) (\(1 \leq i \le n\)) такой, что \(a_i < b_i\) и для всех индексов \(j\) таких, что \(j<i\), выполняется условие \(a_j=b_j\).
Выходные данные
Для каждого набора входных данных в первой строке выведите одно целое число \(cnt\) (\(0 \le cnt \le k\)) — количество выполняемых операций.
Затем во второй строке выведите \(cnt\) целых чисел \(p_1,p_2,\ldots,p_{cnt}\) — \(x\) выбирается равным \(p_i\) для \(i\)-й операции.
Если ответов несколько, то можно вывести любой из них.
Примечание
В первом наборе входных данных:
Изначально \(w=[1,9,2,6,1,8]\). Можно выбрать некоторую вершину \(x\) для выполнения не более одной операции.
- Если \(x=1\), то \(w=[\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2}]\).
- Если \(x=2\), то \(w=[1,\frac{15}{2},2,\frac{15}{2},1,8]\).
- Если \(x=3\), то \(w=[1,9,\frac{11}{3},6,\frac{11}{3},\frac{11}{3}]\).
- Если \(x \in \{4, 5, 6\}\), то \(w=[1,9,2,6,1,8]\).
- Если вы не выполняете никаких операций, то \(w=[1,9,2,6,1,8]\).
\(w\) является лексикографически наименьшим, если \(x=2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
6 1 1
1 9 2 6 1 8
1 2
1 3
2 4
3 6
3 5
7 7 2
3 1 3 3 1 1 2
7 1
7 2
7 4
1 5
2 3
4 6
6 5 1
3 1 3 1 1 3
5 3
5 1
5 6
3 4
1 2
3 2 1
1000000 999999 999997
2 1
1 3
|
1
2
2
1 4
1
5
1
1
|