Одним уютным вечером Алиса решила сыграть в классическую игру «Соедини точки», но с подвохом.
Чтобы начать игру, Алиса рисует прямую линию и отмечает на ней \(n\) точек, проиндексированных числами от \(1\) до \(n\). Изначально между точками нет рёбер, так что все они попарно не соединены. Затем Алиса выполняет \(m\) операций следующего типа:
- Она выбирает три целых числа \(a_i\), \(d_i\) (\(1 \le d_i \le 10\)) и \(k_i\).
- Затем для точек \(a_i, a_i+d_i, a_i+2d_i, a_i+3d_i, \ldots, a_i+k_i\cdot d_i\) Алиса соединяет ребром каждую пару из них.
Алиса хочет узнать, сколько компонент связности\(^\dagger\) образуют эти точки после выполнения всех \(m\) операций.
\(^\dagger\) Считается, что две точки лежат в одной компоненте связности, если между ними есть путь, использующий несколько (возможно, ноль) промежуточных рёбер и вершин.
Выходные данные
Для каждого набора входных данных выведите количество компонент связности.
Примечание
В первом наборе входных данных есть \(n = 10\) точек. Первая операция соединяет точки \(1\), \(3\), \(5\), \(7\) и \(9\). Вторая операция соединяет точки \(2\), \(4\), \(6\), \(8\) и \(10\). В итоге получаем две компоненты связности: \(\{1, 3, 5, 7, 9\}\) и \(\{2, 4, 6, 8, 10\}\).
Во втором наборе входных данных есть \(n = 100\) точек. Единственная операция соединяет точки \(19\), \(21\), \(23\), \(25\) и \(27\). Теперь они образуют одну компоненту связности размера \(5\). Остальные \(95\) точек ни с кем не соединены, так что каждая из них образует отдельную компоненту связности. Значит, ответ равен \(1 + 95 = 96\).
В третьем наборе входных данных есть \(n = 100\) точек. После выполнения всех операций все точки с нечётными номерами от \(1\) до \(79\) образуют одну компоненту связности размера \(40\). Остальные \(60\) точек ни с кем не соединены, так что каждая из них образует отдельную компоненту связности. Значит, ответ равен \(1 + 60 = 61\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
10 2
1 2 4
2 2 4
100 1
19 2 4
100 3
1 2 5
7 2 6
17 2 31
|
2
96
61
|