Bay Area Programming Contest 2026 Novice Division
A. Luxury
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Westin the sheep is located at the lattice point $$$(x,y)$$$. His private jet can travel to any point inside or on the circle centered at $$$(x,y)$$$ with radius $$$r$$$.

There are two countries. Each country is a parallelogram, and a city is located at every lattice point (integer coordinate) that lies inside the parallelogram. The border of the parallelogram counts as inside.

For each country, Westin can visit the cities whose lattice points lie inside or on his circle. Your task is to compare the number of reachable cities in the two countries.

The vertices of each parallelogram are given in the following order:

  • $$$(x_1,y_1)$$$: top-left
  • $$$(x_2,y_2)$$$: top-right
  • $$$(x_3,y_3)$$$: bottom-left
  • $$$(x_4,y_4)$$$: bottom-right

It is guaranteed that for every parallelogram, one pair of opposite sides is parallel to the $$$x$$$-axis (equivalently, the top and bottom edges are horizontal, so $$$y_1=y_2$$$ and $$$y_3=y_4$$$).

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

Each test case consists of three lines:

  • The first line contains three integers $$$x$$$, $$$y$$$, $$$r$$$ ($$$-10^5 \lt x,y \lt 10^5$$$, $$$1 \le r \lt 10^5$$$).
  • The second line contains eight integers $$$x_1\ y_1\ x_2\ y_2\ x_3\ y_3\ x_4\ y_4$$$ describing Country $$$1$$$ ($$$-10^5 \lt x_i,y_i \lt 10^5$$$).
  • The third line contains eight integers $$$x_1\ y_1\ x_2\ y_2\ x_3\ y_3\ x_4\ y_4$$$ describing Country $$$2$$$ ($$$-10^5 \lt x_i,y_i \lt 10^5$$$).

Borders count as inside. It is guaranteed that for every parallelogram, one pair of opposite sides is parallel to the $$$x$$$-axis.

Let $$$n$$$ be the vertical span (in lattice rows) of a country: $$$n = y_1 - y_3 + 1$$$ (since $$$(x_1,y_1)$$$ is top-left and $$$(x_3,y_3)$$$ is bottom-left). It is guaranteed that the sum of $$$n$$$ over all countries across all test cases does not exceed $$$10^5$$$.

Output

For each test case, output one integer:

  • output $$$1$$$ if Country $$$1$$$ has strictly more reachable cities,
  • output $$$2$$$ if Country $$$2$$$ has strictly more reachable cities,
  • output $$$3$$$ if both countries have the same number of reachable cities.
Example
Input
1
0 0 1
-1 1 0 1 0 0 1 0
-1 0 0 0 0 -1 1 -1
Output
3
Note

For the first sample, the following figure illustrates the two parallelograms; both have the same amount of cities inside the radius of the circle, thus the output is $$$3$$$:

B. Clock Creation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Westin is building a clock. He may construct any positive number of gears.

Each gear must receive an integer number of teeth, and every gear must have at least $$$2$$$ teeth. If a gear has $$$x$$$ teeth, it returns to its original position every $$$x$$$ seconds.

All gears rotate together. Starting at time $$$0$$$, every gear advances at a constant rate of 1 tooth per second.

Westin wants that at time $$$k$$$, all gears are simultaneously back in their original positions for the first time.

Among all valid constructions, Westin wants to minimize the total number of teeth used, i.e. $$$a_1 + a_2 + \ldots + a_n$$$ where $$$n$$$ is the number of gears used and $$$a_i$$$ is the number of teeth on gear $$$i$$$.

Determine the minimum possible total number of teeth, and one corresponding construction.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case contains a single integer $$$k$$$ ($$$2 \le k \le 10^5$$$).

Output

For each test case, output:

  • On the first line, print an integer $$$n$$$ — the number of gears used.
  • On the second line, print $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$a_i \ge 2$$$) describing a construction that achieves the minimum.

If multiple optimal constructions exist, print any.

Example
Input
4
2
12
72
210
Output
1
2 
2
4 3 
2
8 9 
4
2 3 5 7

C. Sandwiched Jenga
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The fat sheep and his tiger friend is given a tower of $$$N$$$ distinct Jenga blocks stacked vertically. The blocks are numbered from bottom to top, and the weight of the $$$i$$$-th block from the bottom is $$$w_i$$$. All weights are distinct.

You want to build a second tower by repeatedly removing blocks from the original tower.

A block is considered stable if:

  • If it has both a block above and below it, its weight is strictly less than both adjacent blocks.
  • The top block is always stable.
  • The bottom block is stable if and only if its weight is strictly less than the block above it.
  • A single remaining block in the tower is always stable.

You repeatedly perform the following operation until the original tower becomes empty:

  • Choose any stable block.
  • Remove it from the original tower.
  • Place it on top of your second tower.

Let the resulting second tower be described from bottom to top by the sequence of weights of the removed blocks in the order they were placed.

Your task is to determine the lexicographically greatest possible second tower (from bottom to top) that can be achieved.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.

Each test case consists of two lines:

  • The first line contains a single integer $$$N$$$ ($$$1 \le N \le 10^5$$$).
  • The second line contains $$$N$$$ distinct integers $$$w_1, w_2, \ldots, w_N$$$ ($$$1 \le w_i \le 10^9$$$).

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

Print $$$N$$$ integers representing the lexicographically greatest possible second tower from bottom to top.

Examples
Input
1
4
10 6 9 5
Output
6 5 9 10
Input
4
3
3 10 8
3
14 5 1
6
1 2 3 4 5 6
1
100
Output
8 10 3 
1 5 14 
6 5 4 3 2 1 
100

D. Power Up
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ elements with distinct power levels $$$p_1,p_2,\dots,p_n$$$.

In one operation, you choose two different elements with power levels $$$a$$$ and $$$b$$$ and combine them into a hybrid. The hybrid's power level is

$$$$$$a \cdot b + 2(a+b).$$$$$$

For example, if you choose elements with power levels $$$6$$$ and $$$7$$$, the hybrid has power level $$$6 \cdot 7 + 2 \cdot (6+7) = 68$$$.

You are given $$$q$$$ independent queries. For each query value $$$x$$$, determine whether there exists a pair of different elements from the list such that combining them in one operation produces a hybrid with power level exactly $$$x$$$.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \le n \le 2 \cdot 10^5,\ 1 \le q \le 2 \cdot 10^5)$$$.

The second line contains $$$n$$$ distinct integers $$$p_1,p_2,\dots,p_n$$$ $$$(1 \le p_i \le 2 \cdot 10^5)$$$.

Each of the next $$$q$$$ lines contains one integer $$$x$$$ $$$(1 \le x \le 10^9)$$$ — the value of a query.

Output

For each query, output YES (case-insensitive) if the query value can be obtained by combining some pair of different elements in one operation, and NO (case-insensitive) otherwise.

Examples
Input
5 8
1 3 4 6 7
11
21
26
36
50
68
69
20
Output
YES
NO
YES
YES
YES
YES
NO
YES
Input
4 6
2 4 1 3
8
25
14
11
16
8
Output
YES
NO
YES
YES
YES
YES

E. Transition
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$t$$$ test cases. For each test case, you are given two integers $$$a$$$ and $$$b$$$ ($$$a \lt b$$$), and $$$n$$$ available operations.

The $$$i$$$-th operation is described by a pair $$$(x_i, y_i)$$$:

  • If $$$x_i = 1$$$, then applying this operation changes the current value $$$v$$$ to $$$v + 1$$$.
  • If $$$x_i = 2$$$, then applying this operation changes the current value $$$v$$$ to $$$2v$$$.
  • Applying operation $$$i$$$ costs $$$y_i$$$.

Initially, $$$v = a$$$.

You may apply each operation at most once, in any order. You may only apply an operation if after applying it the value does not exceed $$$b$$$ (i.e., you must keep $$$v \le b$$$ at all times).

Your task is to find the minimum total cost needed to reach exactly $$$v = b$$$. If it is impossible, output $$$-1$$$.

Input
  • The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
  • Each test case starts with a line containing three integers $$$n$$$, $$$a$$$, $$$b$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le a \lt b \le 10^9$$$).
  • The next line contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$x_i \in {1,2}$$$) — the types of the operations.
  • The next line contains $$$n$$$ integers $$$y_1, y_2, \dots, y_n$$$ ($$$0 \le y_i \le 10^9$$$) — the costs of the operations.
  • It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
Output

For each test case, print one integer: the minimum total cost to reach $$$b$$$, or $$$-1$$$ if it is impossible.

Example
Input
2
4 3 10
2 1 1 1
2 5 1 1
2 1 5
2 2
3 4
Output
4
-1
Note

In the first test case, the cheapest way is to use two cheap $$$+1$$$ operations first, then double: $$$3 \to 4 \to 5 \to 10$$$, with total cost $$$1+1+2=4$$$.

In the second test case, only doubling operations are available, so from $$$1$$$ we can reach only $$$2$$$ and $$$4$$$, but never $$$5$$$. Hence the answers are $$$\texttt{4}$$$ and $$$\texttt{-1}$$$.

F. Volcanic Islands
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Volcanoes are erupting over the ovine homeland! Help the Sheep King escape the lava.

There are $$$n$$$ islands connected by $$$m$$$ undirected bridges. Each bridge has a length $$$w$$$: crossing that bridge takes exactly $$$w$$$ days (for both the sheep and the lava).

Each island $$$i$$$ has a volcano that erupts on day $$$a_i$$$. When a volcano erupts, all bridges connected to that island burn down and become unusable.

Lava spreads through the bridge network over time, using the same travel times as the Sheep King (it needs $$$w$$$ days to cross a bridge of length $$$w$$$). If lava reaches an island before its volcano erupts, that island burns at the moment lava arrives.

The Sheep King starts on island $$$1$$$ at day $$$0$$$ and wants to reach island $$$n$$$ to escape. If he arrives at an island exactly when it burns, he is considered safe and may still depart from it at that time.

Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases.

For each test case:

  • The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n \le 10^5,\ 0 \le m \le 10^5)$$$.
  • The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the eruption days of the volcanoes.
  • Each of the next $$$m$$$ lines contains three integers $$$x_j$$$, $$$y_j$$$, and $$$w_j$$$ $$$(1 \le x_j \lt y_j \le n, 1 \le w_j \le 10^9)$$$ denoting an undirected bridge between islands $$$x_j$$$ and $$$y_j$$$ of length $$$w_j$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, print Yes (case-insensitive) if it is possible to travel from island $$$1$$$ to island $$$n$$$. Otherwise, print No (case-insensitive).

Examples
Input
1
3 2
100 2 100
1 2 2
2 3 2
Output
YES
Input
2
5 7
46 34 5 60 36
1 3 23
1 3 29
1 5 7
2 5 25
4 5 8
4 5 11
4 5 29
5 7
25 53 5 49 7
1 2 4
1 4 7
1 5 23
2 5 23
2 5 24
3 4 12
4 5 20
Output
YES
NO
Note

The Sheep King can travel from island $$$1$$$ to island $$$2$$$ in $$$2$$$ days. He arrives at island $$$2$$$ on day $$$2$$$, exactly when it burns. He is still safe, so he can continue to island $$$3$$$ and arrive there on day $$$4$$$. The answer is Yes.

G. Balancing
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

On the Ovine Island, you are in charge of a herd of big fat sheeps.

To protect them from big bad wolves, you have arranged them into an $$$n \times m$$$ rectangular pen ($$$n,m \le 2000$$$). Each cell in the pen is either empty (weight $$$0$$$) or contains a sheep with weight $$$g_{i,j},$$$ an integer between $$$[1,10^6]$$$.

Your boss is wondering if there are special properties of the weights of your sheep.

You are given $$$q$$$ queries, each describing a rectangle. For each rectangle, consider all non-empty weights inside it. Determine whether you can choose three different cells in the rectangle such that if their weights are $$$a,b,c$$$, then the largest of them is strictly less than half of their sum: $$$$$$\max(a,b,c) \lt \frac{a+b+c}{2}.$$$$$$

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 2000$$$).

The next $$$n$$$ lines each contain $$$m$$$ integers $$$g_{i,j}$$$ ($$$0 \le g_{i,j} \le 10^6$$$), where $$$g_{i,j}=0$$$ means the cell is empty.

The next line contains an integer $$$q$$$ ($$$1 \le q \le 10^5$$$).

Each of the next $$$q$$$ lines contains four integers $$$x_1,y_1,x_2,y_2$$$ ($$$1 \le x_1 \le x_2 \le n$$$, $$$1 \le y_1 \le y_2 \le m$$$), describing a rectangle with corners $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ (inclusive).

Output

For each query, print YES (case-insensitive) if there exist three different non-empty cells inside the rectangle whose weights satisfy $$$$$$\max(a,b,c) \lt \frac{a+b+c}{2},$$$$$$ and print NO (case-insensitive) otherwise.

Example
Input
3 3
1 0 0
2 3 10
0 4 0
5
1 1 3 3
2 1 2 3
1 1 2 2
2 1 3 2
1 1 1 1
Output
YES
NO
NO
YES
NO
Note

Query 1: 1 1 3 3

This rectangle covers the entire grid. The non-empty weights inside are: $$$\{1,2,3,10,4\}$$$.

We need three different cells with weights $$$a,b,c$$$ such that $$$\max(a,b,c) \lt \frac{a+b+c}{2}.$$$

Choose the triple $$$(2,3,4)$$$. We have $$$\max(2,3,4) = 4$$$ and $$$\frac{2+3+4}{2} = \frac{9}{2} = 4.5$$$.

Since $$$4 \lt 4.5,$$$ the condition holds.

Therefore, the answer for Query 1 is $$$\texttt{YES}$$$.

$$$ $$$

Query 2: 2 1 2 3

This rectangle covers row $$$2$$$ and columns $$$1$$$ through $$$3$$$. The non-empty weights inside are: $$$\{2,3,10\}$$$.

The only possible triple is $$$(2,3,10)$$$. We have $$$\max(2,3,10) = 10$$$ and $$$\frac{2+3+10}{2} = \frac{15}{2} = 7.5$$$.

Since $$$10 \not \lt 7.5$$$, the condition does not hold.

Therefore, the answer for Query 2 is $$$\texttt{NO}$$$.

H. Alien Attack (Easy Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of Alien Attack. The only differences between this and the hard version are the constraints on the value of $$$n$$$ and $$$q$$$.

Westin is in a country with $$$n$$$ cities and $$$n-1$$$ bidirectional roads. The road network forms a tree. Cities are numbered from $$$1$$$ to $$$n$$$.

Each city $$$v$$$ has a power value $$$p_v(t)$$$ that depends on time $$$t$$$. Initially, at time $$$t=0$$$, every city has power $$$0$$$.

During an alien invasion, meteors may crash into some cities. It is guaranteed that each city is targeted by at most one meteor in total.

If a meteor crashes into city $$$x$$$ at time $$$t_0$$$ with initial energy $$$\textit{val}$$$, then for any time $$$t \ge t_0$$$, the power contributed by that meteor at city $$$x$$$ is:

$$$p_x(t) = \textit{val} - (t - t_0)$$$.

This value can be negative (the meteor keeps losing $$$1$$$ energy per second even after reaching $$$0$$$). Cities that have never been hit by a meteor have power $$$0$$$ at all times.

You are given $$$q$$$ queries of two types:

  • Type 1: $$$1\ t\ x\ val$$$ — a meteor crashes into city $$$x$$$ at time $$$t$$$ with initial energy $$$val$$$. It is guaranteed that city $$$x$$$ has not been targeted before.
  • Type 2: $$$2\ t\ a\ b$$$ — at time $$$t$$$, Westin's friend travels from city $$$a$$$ to city $$$b$$$.

For each type 2 query, output the total power on the simple path from $$$a$$$ to $$$b$$$ at exactly time $$$t$$$:

$$$$$$\sum_{v \in \text{path}(a,b)} p_v(t).$$$$$$
Note that this sum may be negative.
Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2000$$$).

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$), denoting a road between cities $$$u$$$ and $$$v$$$.

The next line contains an integer $$$q$$$ ($$$1 \leq q \leq 5000$$$).

Each of the next $$$q$$$ lines describes a query in one of the following forms:

  • $$$1, t, x, val$$$ ($$$0 \le t \lt 10^9$$$, $$$1 \le x \le n$$$, $$$-10^9 \le \textit{val} \le 10^9$$$),
  • $$$2, t, a, b$$$ ($$$0 \le t \lt 10^9$$$, $$$1 \le a,b \le n$$$).

If at a time t there are both type 1 and type 2 queries, process the type 1 queries first. It is guaranteed that each city appears in at most one type 1 query.

Output

For each type 2 query, output a single integer — the total power on the path from $$$a$$$ to $$$b$$$ at time $$$t$$$.

Example
Input
3
1 2
2 3
4
1 1 2 5
2 2 1 3
2 4 1 3
2 4 2 2
Output
4
2
2
Note

Initially, all cities have power $$$0$$$.

Query 1: $$$1\ 1\ 2\ 5$$$

A meteor hits city $$$2$$$ at time $$$t_0=1$$$ with initial energy $$$5$$$. So for $$$t \ge 1$$$,

$$$p_2(t)=5-(t-1)=6-t.$$$

Query 2: $$$2\ 2\ 1\ 3$$$

At time $$$t=2$$$,

$$$p_2(2)=5-(2-1)=4.$$$
Cities $$$1$$$ and $$$3$$$ still have power $$$0$$$.

Path $$$1 \to 3$$$ is $$$(1,2,3)$$$, so the total is

$$$0+4+0=4.$$$

Query 3: $$$2\ 4\ 1\ 3$$$

At time $$$t=4$$$,

$$$p_2(4)=5-(4-1)=2.$$$
Thus the path sum on $$$1 \to 3$$$ is
$$$0+2+0=2.$$$

Query 4: $$$2\ 4\ 2\ 2$$$

The path from $$$2$$$ to $$$2$$$ contains only city $$$2$$$, so the answer is

$$$p_2(4)=2.$$$

Therefore the outputs are:

$$$4, 2, 2.$$$

I. Toggling Flips
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Donkey has a binary string $$$s$$$ of length $$$n$$$ (each $$$s_i \in \{0,1\}$$$). Positions are indexed from $$$0$$$ to $$$n-1$$$. He also has an energy limit $$$E$$$, an integer $$$k$$$, and an integer $$$m$$$.

Donkey starts at position $$$p = 0$$$ and may perform the following actions in any order:

  • Move: choose any position $$$q$$$ ($$$0 \le q \le n-1$$$) and move from $$$p$$$ to $$$q$$$. This costs $$$|p-q|$$$ energy, and then $$$p$$$ becomes $$$q$$$.
  • Toggle: if $$$p+k \lt n$$$, he may toggle both $$$s_p$$$ and $$$s_{p+k}$$$. If the value to be toggled was $$$0$$$, it becomes $$$1$$$. If it was $$$1$$$, it becomes $$$0$$$. This action costs $$$m$$$ energy. (If $$$p+k \gt = n$$$, this action is illegal.)

The total energy spent on all actions (including both moves and toggles) must not exceed $$$E$$$.

Your task is to determine the maximum possible number of ones in the array after performing any sequence of actions within the energy limit.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2000$$$) — the number of test cases.

Each test case consists of:

  • a line containing four integers $$$n$$$, $$$k$$$, $$$E$$$, and $$$m$$$ $$$(1 \le n \le 500,\ 1 \le k \lt n,\ 0 \le E \le 10^{18},\ 0 \le m \le 10^{18})$$$;
  • a line containing a binary string $$$s$$$ of length $$$n$$$.

It is guaranteed that $$$\left\lfloor \frac{n}{k} \right\rfloor \le 50$$$.

The sum of $$$n$$$ over all test cases will not exceed $$$1000$$$.

Output

For each test case, output a single integer — the maximum possible number of ones in the string after operations with total energy at most $$$E$$$.

Examples
Input
3
5 2 3 1
00000
6 3 2 0
000000
5 2 2 1
10101
Output
4
6
5
Input
6
5 1 10 2
01010
5 2 10 3
00000
5 2 3 5
11111
6 2 100 0
010101
2 1 100 5
00
8 3 7 2
10100101
Output
4
4
5
5
2
8
Note

For the first test case, one optimal sequence is: toggle at $$$p=0$$$ (cost $$$1$$$), move to $$$p=1$$$ (cost $$$1$$$), then toggle at $$$p=1$$$ (cost $$$1$$$). The array changes

$$$$$$00000 \to 10100 \to 11110,$$$$$$
so the maximum number of ones is $$$4$$$.

For the second test case, $$$m=0$$$, so toggles are free and only movement matters. We can toggle at $$$p=0,1,2$$$ with total movement cost $$$2$$$, which turns all positions into $$$1$$$, so the answer is $$$6$$$.

For the third test case, move to $$$p=1$$$ (cost $$$1$$$) and toggle there (cost $$$1$$$). This flips $$$a_1$$$ and $$$a_3$$$ from $$$0$$$ to $$$1$$$, so

$$$$$$10101 \to 11111,$$$$$$
and the answer is $$$5$$$.

J. Best Friends
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have $$$N$$$ friends, numbered $$$1$$$ to $$$N$$$. Each friend chooses exactly one best friend, so the situation can be modeled as a directed graph where every vertex has outdegree $$$1$$$.

For a person $$$v$$$, define $$$\mathrm{indeg}(v)$$$ as the number of people who currently consider $$$v$$$ their best friend (i.e., the indegree of $$$v$$$).

You will process $$$Q$$$ queries of two types:

  • Type 1: 1 x y — person $$$x$$$ changes their best friend to person $$$y$$$.
  • Type 2: 2 — output the MEX of the multiset $$$\{\mathrm{indeg}(1), \mathrm{indeg}(2), \dots, \mathrm{indeg}(N)\}$$$.

The MEX (minimum excluded value) of a multiset of nonnegative integers is the smallest nonnegative integer that does not appear in the multiset.

Input

he first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N \le 5 \cdot 10^4$$$, $$$1 \le Q \le 10^5$$$).

The second line contains $$$N$$$ integers $$$f_1, f_2, \dots, f_N$$$ ($$$1 \le f_i \le N$$$), where $$$f_i$$$ is the current best friend of person $$$i$$$.

Each of the next $$$Q$$$ lines describes a query in one of the following forms:

  • 1 x y ($$$1 \le x, y \le N$$$)
  • 2
Output

For every query of type 2, output a single integer — the MEX of the indegrees of all $$$N$$$ people at that moment.

Example
Input
4 5
3 3 4 2
2
1 4 3
2
1 2 1
2
Output
3
2
3

K. Alien Attack
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the hard version of Alien Attack. The only differences between this and the easy version are the constraints on the value of $$$n$$$ and $$$q$$$.

Westin is in a country with $$$n$$$ cities and $$$n-1$$$ bidirectional roads. The road network forms a tree. Cities are numbered from $$$1$$$ to $$$n$$$.

Each city $$$v$$$ has a power value $$$p_v(t)$$$ that depends on time $$$t$$$. Initially, at time $$$t=0$$$, every city has power $$$0$$$.

During an alien invasion, meteors may crash into some cities. It is guaranteed that each city is targeted by at most one meteor in total.

If a meteor crashes into city $$$x$$$ at time $$$t_0$$$ with initial energy $$$\textit{val}$$$, then for any time $$$t \ge t_0$$$, the power contributed by that meteor at city $$$x$$$ is:

$$$p_x(t) = \textit{val} - (t - t_0)$$$.

This value can be negative (the meteor keeps losing $$$1$$$ energy per second even after reaching $$$0$$$). Cities that have never been hit by a meteor have power $$$0$$$ at all times.

You are given $$$q$$$ queries of two types:

  • Type 1: $$$1\ t\ x\ val$$$ — a meteor crashes into city $$$x$$$ at time $$$t$$$ with initial energy $$$val$$$. It is guaranteed that city $$$x$$$ has not been targeted before.
  • Type 2: $$$2\ t\ a\ b$$$ — at time $$$t$$$, Westin's friend travels from city $$$a$$$ to city $$$b$$$.

For each type 2 query, output the total power on the simple path from $$$a$$$ to $$$b$$$ at exactly time $$$t$$$:

$$$$$$\sum_{v \in \text{path}(a,b)} p_v(t).$$$$$$
Note that this sum may be negative.
Input

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$), denoting a road between cities $$$u$$$ and $$$v$$$.

The next line contains an integer $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$).

Each of the next $$$q$$$ lines describes a query in one of the following forms:

  • $$$1, t, x, val$$$ ($$$0 \le t \lt 10^9$$$, $$$1 \le x \le n$$$, $$$-10^9 \le \textit{val} \le 10^9$$$),
  • $$$2, t, a, b$$$ ($$$0 \le t \lt 10^9$$$, $$$1 \le a,b \le n$$$).

If at a time t there are both type 1 and type 2 queries, process the type 1 queries first. It is guaranteed that each city appears in at most one type 1 query.

Output

For each type 2 query, output a single integer — the total power on the path from $$$a$$$ to $$$b$$$ at time $$$t$$$.

Example
Input
3
1 2
2 3
4
1 1 2 5
2 2 1 3
2 4 1 3
2 4 2 2
Output
4
2
2
Note

Initially, all cities have power $$$0$$$.

Query 1: $$$1\ 1\ 2\ 5$$$

A meteor hits city $$$2$$$ at time $$$t_0=1$$$ with initial energy $$$5$$$. So for $$$t \ge 1$$$,

$$$p_2(t)=5-(t-1)=6-t.$$$

Query 2: $$$2\ 2\ 1\ 3$$$

At time $$$t=2$$$,

$$$p_2(2)=5-(2-1)=4.$$$
Cities $$$1$$$ and $$$3$$$ still have power $$$0$$$.

Path $$$1 \to 3$$$ is $$$(1,2,3)$$$, so the total is

$$$0+4+0=4.$$$

Query 3: $$$2\ 4\ 1\ 3$$$

At time $$$t=4$$$,

$$$p_2(4)=5-(4-1)=2.$$$
Thus the path sum on $$$1 \to 3$$$ is
$$$0+2+0=2.$$$

Query 4: $$$2\ 4\ 2\ 2$$$

The path from $$$2$$$ to $$$2$$$ contains only city $$$2$$$, so the answer is

$$$p_2(4)=2.$$$

Therefore the outputs are:

$$$4, 2, 2.$$$