407023: GYM102688 E The Darkest Timeline

The following content describes a haunting future that may yet come to pass. Reader's discretion is advised.

It is the year 20XX. You have sold your soul to Big Corporation (BgC). It has been decades since you have seen a whimsical, silly problem statement from NOI.PH. Gone are the days of dancing spaghetti and magic zapping pineapples. Now, all you do is make spreadsheets about monthly expenses and file financial reports to your manager. The only programming language you remember using in recent memory is Excel (though sometimes you make a macro in Visual Basic, just to feel alive again).

This is the darkest timeline.

There are $$$n$$$ departments in the company you work for, creatively labeled $$$1, 2, \dots, n$$$. It is very rare for anyone to do their own paperwork in this company. If a form is sent to department $$$i$$$, it will be redirected and sent to department $$$p_i$$$ in the following morning. Of course, then that department will redirect the paperwork again the morning after that, and so on. Nothing ever gets done around here—such is the nature of bureaucracy. Also, note that each $$$p_i$$$ is fixed and will never change, since large corporations love preserving the status quo. On occasion, it is possible that $$$p_i = i$$$, but the paperwork never actually gets done; it just gets endlessly redirected back to the same department, day after day.

Is this... starting to sound like a programming problem...?

The most interesting thing to have happened in the office lately is that your boss was mad that a very important piece of paperwork was sent to one of the departments, and rather than being sent directly to him, it got bounced around and forwarded between different departments until someone realized it was actually important. It was something about tax exemptions? In any case, whichever department first received that paperwork is going to be put on the firing squad. Luckily for them, all the redirecting has made it somewhat hard to track the paperwork's original recipient. Office gossip is vague, so you could only gleam the following details.

• The important paperwork ultimately ended up in one of the following departments: $$$s_1, s_2, \dots s_d$$$.
• After being initially received by some department, the important paperwork was redirected at least $$$r_1$$$ but at most $$$r_2$$$ times before it was discovered.

This sounds like it could be an interesting algorithmic puzzle... You feel... something stirring from within...

You realize it might be an interesting question to ask: Given $$$s_1, s_2, \dots s_d$$$, and $$$r_1$$$ and $$$r_2$$$, what is the set of all possible departments where the important paperwork could have originally been sent to? Since that could possibly be a lot, output the sum of the squares of their labels, instead. Also, you wonder if it is possible to answer $$$q$$$ different queries of this type.

This is your chance to change a future that does not have to be. Answer this problem correctly and you will reignite the spark of passion that competitive programming once brought you. Fail, and you will succumb to life as a corporate drone, forever wondering about a life that could have been.

The first line of input contains $$$t$$$, the number of test cases.

The first line of each test case contains two space-separated integers $$$n$$$ and $$$q$$$.

The second line of each test case contains $$$n$$$ space-separated integers $$$p_1, p_2, \ldots, p_n$$$.

The next $$$2q$$$ lines describe the queries. Each query is described by two lines. The first line of the $$$k$$$th query contains three space-separated integers $$$r_1$$$, $$$r_2$$$ and $$$d$$$. The second line contains $$$d$$$ space-separated integers $$$s_1, s_2, \ldots, s_d$$$.

For each query, output a single line containing a single integer denoting the answer for that query, which is the sum of the squares of the labels of the possible departments where the important paperwork could have originally been sent to.

For all subtasks

$$$1 \le t \le 10$$$

$$$1 \le n, q \le 250000$$$

The sum of all $$$n$$$s across all cases in a single file is $$$\le 250000$$$.

The sum of all $$$q$$$s across all cases in a single file is $$$\le 250000$$$.

The sum of all $$$d$$$s across all cases in a single file is $$$\le 250000$$$.

$$$0 \le r_1 \le r_2 \le 10^9$$$

$$$1 \le d \le n$$$

$$$1 \le p_i \le n$$$

$$$1 \le s_i \le n$$$

The $$$s_i$$$s are distinct for each query.

Subtask 1 (10 points):

$$$n, q \le 300$$$

$$$r_2 \le 300$$$

The sum of the $$$d$$$s across a single test case is $$$\le 300$$$.

Subtask 2 (15 points):

$$$n, q \le 300$$$

The sum of the $$$d$$$s across a single test case is $$$\le 300$$$.

Subtask 3 (15 points):

$$$n, q \le 3000$$$

The sum of the $$$d$$$s across a single test case is $$$\le 3000$$$.

Subtask 4 (16 points):

$$$r_1 = r_2$$$

$$$d = 1$$$

Subtask 5 (15 points):

$$$r_1 = r_2$$$

Subtask 6 (9 points):

$$$d = 1$$$

Subtask 7 (20 points):

No additional constraints.

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

13
13
14
30