410006: GYM103896 H Penguin Problems

Penguin has a very special skill: she is a fitness trainer! She is always helping her friends out by training them to be stronger.

Her $$$N$$$ friends (numbered $$$1$$$ through $$$N$$$) are getting ready for the prestigious International Tug-o-war Competition (ITOWC). The competition lasts $$$D$$$ days and her friends will be competing as $$$T$$$ (potentially overlapping) teams defined as a contiguous array of numbers.

Being professionals, Penguin's friends already have a lot of training. Specifically, friend $$$i$$$ currently has strength $$$s_i$$$. Each team's strength is the sum of each team member's strength.

Penguin wants the best for her friends and has devised a training plan for them! Before each day of the competition, Penguin will train some of her friends, making them more equipped to compete the next day! Each friend that is trained will permanently increase their strength by $$$1$$$.

Given a list of teams, their initial training statuses, and Penguin's training plan, help Penguin compute the strength of each of the teams on each day.

The first line contains three integers, $$$1 \leq N \leq 10^4$$$, $$$1 \leq T \leq 1000$$$, and $$$1 \leq D \leq 100$$$. The second line will contain $$$N$$$ integers $$$0 \leq s_i \leq 1000$$$, the strengths of each friend. The next $$$T$$$ lines will contain two integers, $$$1 \le a_i, b_i \le N$$$, where all friends from $$$a_i$$$ to $$$b_i$$$ inclusive will be on team $$$i$$$. The last $$$D$$$ lines contain an integer $$$1 \leq Q \leq 1000$$$, then $$$Q$$$ more numbers for the friends Penguin will be training.

Print out $$$D$$$ lines, each containing the performance of the teams for that day (following the example format below).

4 3 2
1 2 4 1
1 3
2 4
2 2
2 1 4
3 1 2 3

Day 1: 8 8 2 
Day 2: 11 10 3