There may or may not exist a sequence of nonnegative integers $$$a_1,a_2,\dots,a_n$$$.
You are told that for all $$$1\le i\le n$$$, $$$0\le a_i \lt 10^9+7$$$. You are further given three sequences $$$x_1,x_2,\dots,x_n$$$, $$$y_1,y_2,\dots,y_n$$$, and $$$z_1,z_2,\dots,z_n$$$, and it supposedly holds that for all $$$1\le i\le n$$$,
$$$$$$x_i\left(\sum_{j=1}^ia_j\right)+y_i\left(\sum_{j=i}^na_j\right)\equiv z_i\pmod{10^9+7}$$$$$$
Determine how many sequences $$$a_1,a_2,\dots,a_n$$$ satisfy the given information, and if such sequence is unique, find it.
The first line contains a single integer $$$t$$$, the number of test cases. For each test case:
The first line contains a positive integer $$$n$$$ ($$$1\le 2\times 10^5$$$).
The $$$i$$$-th of the next $$$n$$$ lines contain three integers $$$x_i$$$, $$$y_i$$$ and $$$z_i$$$ ($$$1\le x_i,y_i \lt 10^9+7$$$, $$$0\le z_i \lt 10^9+7$$$).
The sum of $$$n$$$ over all test cases does not exceed $$$2\times 10^5$$$.
For each test case:
Print one line containing one integer, the number of sequences $$$a_1,a_2,\dots,a_n$$$ that satisfy the given information.
Only when the aforementioned integer is $$$1$$$, print another line containing $$$n$$$ integers, representing $$$a_1,a_2,\dots,a_n$$$.
- In the first subtask, worth $$$10$$$ points, $$$n=1$$$.
- In the second subtask, worth $$$19$$$ points, $$$\sum n\le 100$$$.
- In the third subtask, worth $$$19$$$ points, $$$x_i=y_i=1$$$.
- In the fourth subtask, worth $$$22$$$ points, the test data guarantees an unique solution.
- In the final subtask, worth $$$30$$$ points, no additional constraints are posed.
2 3 3 1 9 2 2 16 1 3 15 6 3 6 246 5 7 283 2 7 179 4 6 214 8 7 337 3 5 151
1 1 2 3 1 8 8 0 6 7 8
$$$m$$$ characters play on the SMP, numbered from $$$1$$$ to $$$m$$$. Initially, each character has $$$3$$$ lives; a character is canonically alive if and only if they have a positive number of lives.
The SMP is not peaceful. During wars and other internal conflicts one character may kill another character (possibly themselves). When $$$u$$$ kills $$$v$$$, $$$v$$$ loses one life only when both $$$u$$$ and $$$v$$$ are canonically alive; otherwise, nothing happens.
$$$n$$$ such events have happened, given by pairs two sequences $$$u_1,u_2,\dots,u_n$$$ and $$$v_1,v_2,\dots,v_n$$$. In the $$$i$$$-th such event in chronological order, character $$$u_i$$$ kills $$$v_i$$$.
DreamXD can control lives in alternate universes. For all $$$i$$$ and $$$v$$$ where $$$0\le i\le n$$$ and $$$1\le v\le m$$$, he creates an alternate universe where events happen in the given order, except immediately after the $$$i$$$-th event, where one life is deducted from character $$$v$$$. When $$$i=0$$$, this happens before the first event.
For each integer $$$x$$$ where $$$0\le x\le m$$$, count the number of alternate universes that finish with $$$x$$$ characters canonically alive.
The first line contains two positive integers $$$n$$$ and $$$m$$$ ($$$1\le n\le 6\times 10^4$$$, $$$1\le m\le 10^3$$$).
The $$$i$$$-th of the following $$$n$$$ lines contain two positive integers, representing $$$u_i$$$ and $$$v_i$$$.
Output one line containing $$$m+1$$$ integers: the number of alternate universes that finish with $$$x$$$ characters canonically alive for $$$x=0,1,2,\dots,m$$$.
- In the first subtask, worth $$$5$$$ points, $$$n\le 5$$$ and $$$m=1$$$.
- In the second subtask, worth $$$11$$$ points, $$$n,m\le 100$$$.
- In the third subtask, worth $$$41$$$ points, $$$n\le 10^3$$$.
- In the final subtask, worth $$$43$$$ points, no additional constraints are posed.
2 2 1 2 1 2
0 3 3
You are given a tree with $$$n$$$ nodes, labeled $$$1\dots n$$$ and rooted at $$$1$$$. The weight of the $$$i$$$-th node is an integer $$$a_i$$$.
There are $$$m$$$ scenarios, denoted by a node $$$u$$$ and an integer $$$x$$$. For each scenario, suppose we increase the weight of all nodes in the subtree of $$$u$$$ by $$$x$$$; over all connected induced subgraphs of the subtree of $$$u$$$ containing $$$u$$$, what is maximum possible sum of node weights of such a subgraph?
The first line contains two integers $$$n$$$ and $$$m$$$, the number of nodes and the number of scenarios, respectively ($$$1\le n,m\le 10^6$$$).
The second line contains $$$n-1$$$ integers $$$f_2,f_3,\dots,f_n$$$, where $$$f_i$$$ is the father of node $$$i$$$ ($$$1\le f_i \lt i$$$).
The third line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$|a_i|\le 10^8$$$).
The $$$i$$$-th of the following $$$m$$$ lines contain two integers $$$u$$$ and $$$x$$$ ($$$1\le u\le n$$$, $$$|x|\le 10^8$$$) corresponding to one scenario.
For each scenario, output one line, corresponding to the maximum possible sum of node weights of the described subgraph in this scenario.
- In the first subtask, worth $$$5$$$ points, $$$n,m\le 1000$$$.
- In the second subtask, worth $$$10$$$ points, $$$n,m\le 10^5$$$ and $$$|a_i|,|x| \lt 50$$$.
- In the third subtask, worth $$$15$$$ points, $$$n\le 1000$$$.
- In the fourth subtask, worth $$$47$$$ points, $$$n,m\le 10^5$$$.
- In the final subtask, worth $$$23$$$ points, no additional constraints are posed.
10 6 1 1 2 2 3 5 5 5 6 5 2 3 1 -5 -7 1 1 1 2 1 0 1 -2 1 3 2 1 5 0 5 -2
11 4 34 7 -2 -7
Dream abstracts the fabric of spacetime as a directed rooted tree (arborescence) with $$$n$$$ nodes (numbered $$$1$$$ through $$$n$$$). Node $$$1$$$ is the root and for each $$$i$$$ from $$$2$$$ to $$$n$$$, the parent of node $$$i$$$ is $$$f_i$$$. All edges of this tree are directed away from the root; let this graph be $$$T$$$.
Consider $$$m$$$ additional directed edges $$$(u_1,v_1),(u_2,v_2),\dots,(u_m,v_m)$$$; let this graph be $$$E$$$. $$$T\cup U$$$ is a directed acyclic graph.
Dream considers a pair of nodes $$$(i,j)$$$ to be plausible with respect to a graph $$$G$$$ if there is a path in $$$G$$$ from $$$i$$$ to $$$j$$$. Let $$$f(G,l,r)$$$ where $$$1\le l\le r\le n$$$ be the number of pairs $$$(i,j)$$$ such that $$$l\le i \lt j\le r$$$ and $$$(i,j)$$$ is plausible with respect to $$$G$$$.
Dream now wants you to answer $$$q$$$ queries of the following form: for two integers $$$l,r$$$ where $$$1\le l\le r\le n$$$, find $$$f(T\cup U,l,r)-f(T,l,r)$$$.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2\le n\le 7\times 10^5$$$, $$$0\le m\le 100$$$).
The second line contains $$$n-1$$$ integers $$$f_2,f_3,\dots,f_n$$$, indicating that there is an edge from $$$f_i$$$ to $$$i$$$. The test data guarantees that this forms an arborescence.
The $$$i$$$-th of the next $$$m$$$ lines contain two integers $$$u_i$$$ and $$$v_i$$$, describing an additional edge. The test data guarantees $$$T\cup U$$$ is a DAG.
The next line contains an integer $$$q$$$ ($$$1\le q\le 3\times 10^5$$$).
The next $$$q$$$ lines contain two integers $$$l$$$ and $$$r$$$, describing a query.
For each query, output on one line the answer to that query.
- In the first subtask, worth $$$3$$$ points, $$$n,q\le 1000$$$.
- In the second subtask, worth $$$29$$$ points, $$$n,q\le 2\times 10^5$$$ and $$$m\le 50$$$.
- In the third subtask, worth $$$31$$$ points, $$$m\le 50$$$.
- In the final subtask, worth $$$37$$$ points, no additional constraints are posed.
2 2 1 1 2 1 2 1 1 2
0
8 2 1 2 5 1 4 3 3 2 4 4 7 3 4 6 5 7 1 8
0 1 4
Let $$$f(\prod p_i^{a_i})=\sum a_ip_i$$$, where $$$p_i$$$ are primes. In particular, $$$f(1)=0$$$.
Define $$$g(n,k,r)$$$ to be the sum of all $$$i^k$$$ where $$$i$$$ is a positive integer less than $$$n$$$ and $$$f(i)\equiv r\pmod 4$$$.
Given $$$m$$$ and $$$k\in\{0,1\}$$$, for all integers $$$i$$$ where $$$1\le i\le \lfloor\sqrt m\rfloor$$$, find $$$g(\lfloor\frac{m}{i}\rfloor,k,0\dots 3)$$$.
The first line contains two integers $$$m$$$ and $$$k$$$ ($$$1\le m\le 10^{10}$$$, $$$0\le k\le 1$$$).
Output $$$\lfloor\sqrt m\rfloor$$$ lines. The $$$i$$$-th of these lines should contain four integers, corresponding to $$$g(\lfloor\frac{m}{i}\rfloor,k,0)$$$, $$$g(\lfloor\frac{m}{i}\rfloor,k,1)$$$, $$$g(\lfloor\frac{m}{i}\rfloor,k,2)$$$, and $$$g(\lfloor\frac{m}{i}\rfloor,k,3)$$$, respectively.
- In the first subtask, worth $$$5$$$ points, $$$m\le 10^7$$$.
- In the second subtask, worth $$$15$$$ points, $$$n\le 10^9$$$ and $$$k=0$$$.
- In the third subtask, worth $$$25$$$ points, $$$k=0$$$.
- In the fourth subtask, worth $$$25$$$ points, $$$n\le 10^9$$$.
- In the final subtask, worth $$$30$$$ points, no additional constraints are posed.
10 0
2 2 3 3 2 1 1 1 1 0 1 1
10 1
5 11 19 20 5 5 2 3 1 0 2 3