A + B is a problem used to test one's basic knowledge for competitive programming. Here is yet another boring variation of it.
You have two integers, A and B. You want to make them equal. To do so, you can perform several steps, where each step is one of the following:
- A+=A
- A+=B
- B+=A
- B+=B
Unfortunately, A + B is a hard problem for us, so you are allowed to make at most 5000 steps.
Two integers A, B are given. (1 ≤ A, B ≤ 1018).
In the first line, print a single integer n (0 ≤ n ≤ 5000) denoting the number of steps.
In next n lines, print one of the following strings to denote your desired operation: "A+=A", "A+=B", "B+=A", or "B+=B".
Any sequence of steps that yields the desired result will be judged correct.
2 3
4
B+=B
B+=A
A+=A
A+=A
MolaMola is a world-famous rock band composed of three members: Guitarist Sangsoo cki86201 Park famous for his amazing performance with Link-cut tree, drummer Sunggwan dotorya Park who plays 5 problems in 10 minutes without single WA, and the vocalist Bumsoo zlzmsrhak Park who is responsible for the impressive outlook of the band. The movie about their story, Bohemian Rhaksody, became a blockbuster in Korea, and they are preparing for their perfect comeback concert.
Bumsoo, famous for his unique sense of fashion, thinks that perfect concerts need not only the best music but also great visual effects. Needless to say, the illumination setting is a very important matter for him.
The stage given to them is a $$$H \times W$$$ size rectangle with four corners in $$$(0, 0), (0, W), (H, 0), (H, W)$$$, and there are $$$N$$$ bulbs already installed in the stage. Note that the bulbs may lie on the boundary, but are not strictly outside. To prevent interference, each bulb has a distinct $$$x$$$-coordinate, and each bulb also has a distinct $$$y$$$-coordinate. Every bulb is designed to light either the east/west/south/north part of the stage. More formally, the bulb at the coordinate $$$(X, Y)$$$ can be operated in one of the following modes:
- Light the area of the stage where $$$x \le X$$$.
- Light the area of the stage where $$$x \ge X$$$.
- Light the area of the stage where $$$y \le Y$$$.
- Light the area of the stage where $$$y \ge Y$$$.
Bumsoo wants their band to play in the brightest area, so the stage will be exactly the area that is lit by all $$$N$$$ bulbs. Now, Bumsoo wants to find a way to operate the bulbs, in order to maximize the area of their stage. Help him!
The first line contains three integers $$$H, W, N$$$. ($$$1 \le N \le 100000, 1 \le H, W \le 10^8$$$)
In the next $$$N$$$ lines, two integers $$$X, Y$$$ are given, indicating that the bulb is installed in coordinate $$$(X, Y)$$$. ($$$0 \le X \le H, 0 \le Y \le W$$$)
It is guaranteed that no pair of different bulbs share an $$$x$$$-coordinate, and no pair of different bulbs share a $$$y$$$-coordinate.
Print the maximum possible area that can be lit by all $$$N$$$ bulbs.
4 4 5 0 4 1 3 2 2 3 1 4 0
6
100000000 100000000 1 0 0
10000000000000000
100000000 100000000 12 100000000 59411855 0 4914151 57454627 45388814 93661922 93279520 81531691 0 5221549 64790529 75886863 85609174 74950464 100000000 18493301 57818271 66752434 90450964 44757377 54518291 99631520 21997156
4522156529817280
A Cactus graph is a simple connected undirected graph where each edge lies in at most one simple cycle.
An adjacency matrix of a $$$N$$$-vertex graph is a $$$N\times N$$$ integer matrix, where $$$A_{i, j}$$$ is $$$1$$$ if there exists an edge connecting vertex $$$i$$$ and $$$j$$$, and $$$0$$$ otherwise.
The Determinant of a $$$N\times N$$$ matrix is defined as $$$\sum_{p \in P(N)}{(-1)^{inv(p)}(\prod_{i=1}^{n}{A_{i, p_i}})}$$$ , where $$$P(N)$$$ is the set of all permutations of size-$$$N$$$, and $$$inv(p)$$$ is the number of pairs $$$1 \le i \lt j \le N$$$ such that $$$p_i \gt p_j$$$.
993244853 is a prime number that looks like $$$998244353 = 119 \times 2^{23} + 1$$$, but is actually not.
This problem asks you to calculate the determinant of an adjacency matrix of given cactus graph mod $$$993244853$$$.
The first line contains $$$N, M$$$, denoting the number of vertices and edges of the cactus graph. ($$$1 \le N \le 50000, 0 \le M \le 250000$$$)
In the next $$$M$$$ lines, two distinct integers $$$s, e$$$ denoting each endpoint of the edges are given. ($$$1 \le s, e \le N, s \neq e$$$).
It is guaranteed that the graph is connected, it does not contain loops or multiple edges, and every edge belongs to at most one simple cycle.
Print the determinant of an adjacency matrix of given cactus graph mod 993244853.
6 6 2 3 5 6 2 5 1 2 3 4 6 2
993244852
1 0
0
10 11 1 2 3 4 1 3 5 6 7 8 9 10 7 9 6 8 1 9 10 5 4 9
993244849
To celebrate your team's victory at ICPC World Finals, Edsger W. Dijkstra (The inventor and namesake of Dijkstra's algorithm) will throw a fabulous party at your house in New York City. The party starts in 5 hours, so he should better start moving.
New York City is modeled as a 2-dimensional plane. Dijkstra is now in coordinate $$$(s_x, s_y)$$$, and your house is located in coordinate $$$(e_x, e_y)$$$. Dijkstra should come to your house by only moving in a direction parallel to the coordinate axes (you remember the Manhattan distance, right?). Also, there are $$$N$$$ skyscraper in an axis-parallel rectangular shape, which you can pass through its boundary, but cannot pass through anywhere strictly inside of it.
You got a phone call from Dijkstra, saying that it's too hard for him to compute the shortest path between his location and your house. Somehow, he is losing his edge. However, that's not bad news, because it's a chance for you to be cool in front of the great Dijkstra. Can you?
It is guaranteed that all $$$x$$$ coordinates are distinct and all $$$y$$$ coordinates are distinct. It is also guaranteed that no pair of rectangles overlap. It is also guaranteed that your house and Dijkstra's starting location are not inside of any rectangles.
The first line contains five integers $$$N, s_x, s_y, e_x, e_y$$$. ($$$1 \le N \le 250 000, 0 \le s_x, s_y, e_x, e_y \le 10^8$$$)
The next $$$N$$$ lines contain four integers $$$a_i, b_i, c_i, d_i$$$. This indicates that $$$i$$$-th skyscraper is a rectangle with its four corners located in $$$(a_i, b_i), (a_i, d_i), (c_i, b_i), (c_i, d_i)$$$. ($$$0 \le a_i \lt c_i \le 10^8$$$, $$$0 \le b_i \lt d_i \le 10^8$$$).
It is guaranteed that:
- Let $$$X = \{s_x, e_x, a_1, a_2, \cdots, a_N, c_1, c_2, \cdots, c_N\}, Y = \{s_y, e_y, b_1, b_2, \cdots, b_N, d_1, d_2, \cdots, d_N\}$$$. All elements in $$$X$$$ are distinct, and all elements in $$$Y$$$ are distinct.
- No pair of rectangles share a common point.
- Dijkstra's location and your house's location are not in any of the rectangles.
Print the length of the shortest path between Dijkstra's location and your house, using the Manhattan metric.
3 2 14 5 1 4 6 6 10 0 7 3 9 1 2 8 5
20
1 0 500 100 503 1 0 99 1000
1097
2 2 8 10 3 3 6 6 10 7 1 8 7
15
Ho has arrived in a secret place for her secret business trip. She knows her trip will take at most N days or shorter but doesn't know the exact number of days she'll be there. So, the perfectionist Ho wants to make the daily meal lists for every possible trip length, 1 day to N days.
There is the only food court that offers exactly 2N kinds of menus (by accident) in this secret place. The food court opens only lunch time and dinner time, and oddly, the prices of lunch and dinner for the same menu can be different.
She will eat exactly one menu per lunch and dinner respectively and never eat the same menu for the entire of the trip. She never minds about which kind of menu will be her meal, the only important thing is the entire price of meals must be minimized.
Under these conditions, she can make her meal lists but realizes that writing every N(N + 1) menu is hard and tiresome. So, instead of making the meal lists, she calculates the minimized entire price for i lunch menus and i dinner menus where i = 1 to N.
You, the big fan of Ho, has a supreme task. Print the N prices she calculated.
The first line contains an integer N. (1 ≤ N ≤ 250000)
In the next 2N lines, each line contains two integer l, d denoting the prices of the menus when lunch and dinner respectively. (1 ≤ l, d ≤ 109)
Print N lines. The i-th line should contain an integer denoting the minimized entire price for i lunch menus and i dinner menus.
1
4 9
5 3
7
2
1 6
2 4
5 3
3 1
2
7
4
7 5
5 7
7 4
4 2
2 5
6 4
3 2
1 9
3
7
16
26
In the backyard of Seoul Science High School, there is a magical tree with $$$N$$$ vertices, where every vertex contains a single fruit. (A tree is a connected undirected graph with $$$N-1$$$ edges.)
Although it is prohibited to pick any fruits from the tree, students naturally want to secretly pick some fruit to eat. To prevent being caught by the teacher, they use the following procedure to choose a fruit to pick:
- Choose two vertex $$$s, e$$$ in the tree, and consider all fruits lying in the unique path from $$$s$$$ to $$$e$$$. Fruits in vertex $$$s, e$$$ are also considered.
- Among the fruits in a path, if there is a type of fruit that forms a majority, student pick that fruit and eat. A type of fruit forms a majority if the count of such fruits in a path is strictly larger than half of the total number of fruits in the path.
Of course, they are very nice students, so they never actually pick any of the fruits. They simply think of it. :)
Being exceptionally nice students, they naturally extended their thought experiment as a query problem. Thus, given $$$Q$$$ independent queries, you should find the answer or state that no majority exists. Can you solve it?
The first line contains two integers $$$N, Q$$$. ($$$1 \le N, Q \le 250 000$$$).
In the next line, $$$N$$$ integers $$$c_i$$$ is given, denoting the type of fruit in vertex $$$i$$$. ($$$1 \le c_i \le N$$$).
In the next $$$N-1$$$ lines, two integers $$$a_i, b_i$$$ denoting endpoints of each edge are given. ($$$1 \le a_i, b_i \le N, a_i \neq b_i$$$).
In the next $$$Q$$$ lines, two integers $$$s_i, e_i$$$ denoting two endpoints of each path are given. ($$$1 \le s_i, e_i \le N$$$).
Print $$$Q$$$ lines. For each line, print a single integer denoting the type of fruit that forms a majority in a given path. If there exists no majority in the given path, print $$$-1$$$.
7 4 3 1 1 2 1 1 2 1 3 7 5 2 3 5 3 5 6 4 5 1 4 7 2 3 3 4 7
-1 1 1 2
Seunghyun is a mathematician, and he likes good jokes.
For a set U = {0, 1, ..., 2k - 1}, a nonempty subset 
is good if it satisfies the following rules.
- for any
, their bitwise-and 
should be in S. - for any , their bitwise-or
should be in S.
You are given n distinct integers in [0, 2k - 1] range. Find the number of good sets which contains all n integers.
The first line contains two integers k, n. (1 ≤ k ≤ 7, 0 ≤ n ≤ 2k)
The next line contains n distinct integers a1, a2, ..., an(0 ≤ ai ≤ 2k - 1).
Print a single integer denoting the number of good sets.
2 1
0
7
4 3
1 2 7
29
You are given a tree with $$$N$$$ vertices and $$$N-1$$$ edges. Vertex 1 is the root of the tree. Every vertex is associated with three positive integers $$$A_i, B_i, C_i$$$, where $$$C_1 = 10^9$$$ and $$$B_{parent(x)} \le B_x$$$ for all $$$x \neq 1$$$, where $$$parent(x)$$$ is the parent node of $$$x$$$.
If you see a tree with numbers, you naturally want to ask some queries. For each query, you are given a vertex $$$V$$$ and number $$$T$$$. Then, you should find a minimum value of $$$A_i + B_i \times T$$$, for all vertex $$$i$$$ which lies in some shortest path between vertex $$$1$$$ and $$$V$$$, and which satisfies $$$C_i \geq T$$$. Note that, if $$$T \le 10^9$$$, then there exists a minimum value.
In the first line, two integers $$$N, Q$$$ are given. ($$$1 \le N \le 80000, 1 \le Q \le 160000$$$).
In the next line, $$$N$$$ integers $$$A_1, A_2, \cdots, A_N$$$ are given. ($$$1 \le A_i \le 10^9$$$)
In the next line, $$$N$$$ integers $$$B_1, B_2, \cdots, B_N$$$ are given. ($$$1 \le B_i \le 10^9$$$)
In the next line, $$$N$$$ integers $$$C_1, C_2, \cdots, C_N$$$ are given. ($$$1 \le C_i \le 10^9$$$)
In the next $$$N-1$$$ lines, two integers $$$X, Y$$$ denoting the endpoints of edges are given. ($$$1 \le X, Y \le N$$$)
In the next $$$Q$$$ lines, two integers $$$V, T$$$ denoting the arguments of queries are given. ($$$1 \le V \le N, 0 \le T \le 10^9$$$)
It is guaranteed that $$$C_1 = 10^9$$$, and $$$B_{parent(x)} \le B_x$$$ for all $$$x \neq 1$$$, when $$$parent(x)$$$ is the parent node of $$$x$$$.
Print $$$Q$$$ lines. In each line, print a single integer which is the minimum value asked by the given query.
5 2 5 4 3 2 1 1 2 3 4 5 1000000000 2 4 5 2 1 2 1 3 2 4 2 5 4 0 4 2
2 7
You are given a permutation of size $$$N$$$. For each $$$i$$$, print the number of indices $$$j \neq i$$$, which when removed, decreases the maximum possible length of an increasing subsequence that contains index $$$i$$$.
The first line contains an integer $$$N$$$. ($$$1 \le N \le 250000$$$).
The next line contains $$$N$$$ integers $$$A_1, A_2, \cdots, A_N$$$ denoting the permutation. ($$$1 \le A_i \le N$$$, all $$$A_i$$$s are distinct).
Print $$$N$$$ integers, separated by spaces, denoting the answers for $$$i = 1, 2, 3, \cdots, N$$$.
1 1
0
6 1 2 3 4 5 6
5 5 5 5 5 5
6 6 5 4 3 2 1
0 0 0 0 0 0
4 2 1 4 3
0 0 0 0
9 1 2 3 6 5 4 7 8 9
5 5 5 6 6 6 5 5 5
There are $$$N$$$ teachers and $$$N$$$ students in the Seoul Science High School. Each student bought $$$N$$$ flowers because tomorrow is a teacher's day in Korea. However, one of the students quit, and now only $$$N-1$$$ students remain in the school.
Teachers are very jealous, so they will give an F grade to students when they receive fewer flowers from that student than others. Therefore, every teacher should receive exactly $$$N-1$$$ flowers. A student can only give flowers to teachers who have taught him or her, and you know which students have learned from which teachers.
Younghun is the student of Seoul Science High School, and he needs your help in organizing this event.
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$2 \le N \le 100 000$$$, $$$1 \le M \le 200 000$$$) describing the number of teachers and the number of (student, teacher) pairs where the student learned from the teacher.
In the next $$$M$$$ lines describe the relations: $$$j$$$-th line contains two integers $$$s_j$$$, $$$t_j$$$ ($$$1 \le s_j \le N-1$$$, $$$1 \le t_j \le N$$$) indicating that $$$s_j$$$-th student can give flowers to the $$$t_j$$$-th teacher. It is guaranteed that all pairs are different.
If it is impossible to give all teachers the same number of flowers ($$$N-1$$$ flowers), print a single number $$$-1$$$ in the first line.
Otherwise, your program should output $$$M$$$ lines. In $$$j$$$-th line, there should be a single integer denoting the number of flowers which $$$s_j$$$-th student gave to $$$t_j$$$-th teacher.
If there are multiple possible answers, you can output any of them.
6 12 1 3 1 4 1 5 2 2 2 4 3 1 3 3 4 1 4 2 4 4 5 4 5 6
1 0 5 5 1 2 4 3 0 3 1 5
6 12 1 2 1 3 1 4 2 2 2 4 3 1 3 3 4 1 4 2 4 4 5 5 5 6
-1