Một năm nữa lại trôi qua và một năm mới đang đến gần với chúng ta. Đối với flo, năm vừa qua là một năm không có gì là may mắn, khá thăng trầm nhưng cũng để lại trong tâm trí cậu nhiều kỉ niệm khó nhớ. Một trong số đó có lẽ là những ngày ôn tập chuẩn bị cho kì thi cuối kì I của flo diễn ra trong $2$ tuần. Trong thời gian đó, cậu đã phải chịu đựng nhiều đau đớn và trải qua nhiều khó khăn. Nhưng rồi kì thi ấy cũng trôi qua, kết quả mà flo đạt được đã vượt xa mong đợi của cậu. Vì thế mà flo vô cùng vui bởi kết quả cho những đau đớn mà cậu trải qua lại vô cùng xứng đáng.

Năm mới đã đến và kết quả thi cử của flo rất tốt nên cậu đã được mẹ cậu thưởng $n$ hộp kẹo với vô vàng loại kẹo khác nhau. Những hộp kẹo này còn có cho mình $1$ độ ngon nhất định khi hộp thứ $i$ có độ ngon là $a_i$. Tuy nhiên nếu ăn hết bây giờ thì sẽ quá lãng phí nên flo quyết định ăn $n$ hộp kẹo này trong những ngày tới. Mỗi ngày, cậu sẽ chọn $1$ số nguyên dương $m$ bất kỳ và ăn $m$ viên kẹo đầu tiên sao cho độ phong phú của $m$ hộp kẹo đó giao động từ $l$ đến $r$. Đối với flo, độ phong phú của một dãy hộp kẹo là số lượng độ ngon khác nhau của các hộp kẹo đó. Khi ăn như vậy sẽ giúp cậu có thể cảm nhận được sự hòa quyện của các loại kẹo với nhau, từ đó tạo nên một vị ngon khó cưỡng.

Vì là một con người coi trọng việc tiết kiệm, flo muốn ăn theo cách trên nhưng cậu phải ăn hết kẹo mà không chưa lại hộp kẹo nào. Tuy nhiên do số lượng hộp kẹo mà mẹ của flo tặng cho cậu quá lớn làm cho cậu không biết phải phân chia để ăn như thế nào mới có thể thỏa mãn được cậu. Bạn hãy tính giúp flo nhé.

3 1 2
2 3 2

4

6 2 4
1 2 1 3 2 2

3