В городе живут \(m\) людей. Также в городе есть в продаже \(n\) блюд, где \(i\)-е блюде имеет цену \(p_i\), уровень \(s_i\) и симпатичность \(b_i\). У \(j\)-го человека есть доход \(inc_j\) и предпочтительная симпатичность \(pref_j\).
Ни один человек никогда не купит блюдо, уровень которого ниже, чем его доход. Также, ни один человек не может позволить купить себе блюдо, с ценой выше, чем его доход. Иными словами, человек \(j\) может купить блюдо \(i\), если \(p_i \leq inc_j \leq s_i\).
Также человек \(j\) может купить блюдо \(i\), только если \(|b_i-pref_j| \leq (inc_j-p_i)\). Иначе говоря, если цена блюда на \(k\) меньше, чем доход какого-то человека, то этот человек согласен на не более чем \(k\) абсолютную разницу между симпатичностью блюда и предпочитаемой симпатичностью этого человека.
Выведите количество блюд, которые может купить каждый человек в городе.
Выходные данные
Выведите \(m\) целых чисел — количество блюд, которые может купить каждый человек, живущий в городе.
Примечание
В первом примере первый человек может купить блюдо \(2\), второй человек может купить блюда \(1\) и \(2\), а третий человек не может купить ни одного блюда.
Во втором примере первый человек не может купить ни одного блюда, второй человек может купить блюда \(1\) и \(4\), а третий человек может купить блюда \(1\), \(2\) и \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
2 1 3
2 4 4
2 1 1
2 2 3
1 2 4
|
1 2 0
|
|
2
|
4 3
1 2 1 1
3 3 1 3
2 1 3 2
1 1 3
1 2 1
|
0 2 3
|