title: [ICPC2021 WF] Islands from the Sky

description:
You might never have heard of the island group of Iceepeecee, but that suits their inhabitants just fine. Located in a remote part of the South Pacific, they are truly off the beaten track, without any regular air or sea traffic, and they have remained a tropical paradise with unspoiled local fauna and flora.

Being off the map is great when you don't want to be overrun by hordes of tourists, but not so ideal when you actually do need a map for some reason. One such reason came up recently: Iceepeecee's central government needs an exact map of the islands to apportion government funds. Even tropical paradises need money, so Iceepeecee needs a map!

The easiest way to create a map would be an aerial survey. After dismissing chartering planes as too expensive, building an air balloon as too dangerous, and fitting carrier pigeons with cameras as too cruel to animals, they had a brilliant idea. Even with its remote location, there are still plenty of commercial airplanes crossing the skies above Iceepeecee. What if one mounted cameras on flights that are already scheduled to fly anyway? That would be a cheap solution to the problem!

Iceepeecee's plan is to install line-scan cameras on the planes. These cameras point straight downwards and collect images one line segment at a time, orthogonal to the flight path. The photographed line segment will be determined by the altitude that the plane is flying at, and the camera's aperture angle $\theta$ (see Figure F.1). Greater angles $\theta$ mean that the camera can see more, but also that the camera is more expensive.

Moreover, Iceepeecee wants to make sure that each island is observed in its entirety by at least one flight. That means it is not sufficient that an island is only partially photographed by multiple flights, even if the combination of the photographs covers the whole island.

![](https://cdn.luogu.com.cn/upload/image_hosting/99wwtofi.png)

Figure F.1: A view of the plane, shown head-on. Its camera points downward and can see the part of the ground underneath the plane that is shown in green. How much is visible depends on the aperture angle $\theta$.

Flight paths follow straight line segments in three-dimensional space, that is, ($x_1, y_1, z_1$) $-$ ($x_2, y_2, z_2$) (see Figure F.2), where the $z$-coordinates give the altitude of the plane. Photographs are taken only along these line segments.

Given the location of their islands and flights, Iceepeecee wants to find the smallest aperture angle $\theta$ that allows for a successful survey. Can you help?

![](https://cdn.luogu.com.cn/upload/image_hosting/3pdn3q1b.png)

Figure F.2: Three islands (shown in black) and two flight paths (red and green). Altitudes are not shown. The shaded areas represent the ground visible on the two flight paths for an optimally chosen $\theta$. This corresponds to the first sample input.Three islands (shown in black) and two flight paths (red and green). Altitudes are not shown. The shaded areas represent the ground visible on the two flight paths for an optimally chosen $\theta$. This corresponds to the first sample input.

inputFormat:
The input describes a set of islands and flight paths. It starts with a line containing two integers $n$ and $m$, the number $n$ of islands, and the number $m$ of flight paths, respectively ($1 \leq n,m \leq 100$). This is followed by descriptions of the $n$ islands. Each island description starts with a line containing a single integer $n_i$, the number of vertices of the polygon describing the $i^{th}$ island ($3 \leq n_i \leq 100$). It is followed by $n_i$ lines, each containing two integers $x_{ij}$, $y_{ij}$ ($|x_{ij}|, |y_{ij}| \leq 10^6$), specifying the vertices for the $i^{th}$ island in counterclockwise order. Each island's polygon is simple, that is, its vertices are distinct and no two edges of the polygon intersect or touch, other than consecutive edges which touch at their common vertex. Different islands do not intersect or touch.

The input concludes with another $m$ lines, each describing a flight path. Each such line contains six integers $x_1$, $y_1$, $z_1$, $x_2$, $y_2$, $z_2$ ($|x_i|, |y_i|, |z_i| \leq 10^6$, $z_i > 0$ and ($x_1, y_1$) $\neq$ ($x_2, y_2$)). They specify that a flight takes place from ($x_1, y_1, z_1$) to ($x_2, y_2, z_2$).

outputFormat: Output the smallest angle $\theta$ (in degrees) that allows for a complete survey of the islands with the given flights. The answer should be exact to an absolute or relative error of $10^{-6}$. If there is no such angle, then output $\texttt{impossible}$. The input is chosen such that if the coordinates of the island vertices are changed by at most $\pm 10^{-8}$, then the answer will not change more than the allowed rounding error.

translation:
有一个空间直角坐标系 $O-xyz$，在坐标平面 $xOy$ 上有 $n$ 个岛，每个岛是一个简单多边形。保证岛屿之间不重叠。

坐标系中有 $m$ 条飞机航线，航线是一条线段，两个端点的坐标分别是 $(x_1,y_1,z_1)$ 和 $(x_2,y_2,z_2)$。飞机可以沿任意一条飞机航线飞行。

现在要在飞机上装扫描相机。扫描相机的能扫描的范围取决于角度 $\theta$。

飞机位于一点 $(x,y,z)$ 时，我们可以以 $(x,y,z)$ 为顶点做一个顶角为 $2\theta$ 的等腰三角形，这个等腰三角形所在的面和坐标平面 $xOy$ 垂直，同时也和这架飞机所在的飞机航线到坐标平面 $xOy$的投影垂直。
将飞机位于 $(x,y,z)$ 时，能扫描到的线段定义为这个等腰三角形的底边。

对于一条航线，其覆盖的范围定义为当飞机在这条航线上运动时，所有能扫描到的线段组成的四边形。

求最小的 $\theta$（角度制），使得每个岛都至少完全位于一条航线的覆盖范围内。如果无论 $\theta$ 取何值都不能满足条件，输出 `impossible`。

$1\le n,m\le 100$，多边形的边数不超过 $100$，所有给出的坐标绝对值不超过 $10^6$。


title: [ICPC2021 WF] Mosaic Browsing

type: P

description:
The International Center for the Preservation of Ceramics (ICPC) is searching for motifs in some ancient mosaics. According to the ICPC's definition, a $\textit{mosaic}$ is a rectangular grid where each grid square contains a colored tile. A $\textit{motif}$ is similar to a mosaic but some of the grid squares can be empty. Figure G.1 shows an example motif and mosaic.

The rows of an $r_q \times c_q$ mosaic are numbered $1$ to $r_q$ from top to bottom, and the columns are numbered $1$ to $c_q$ from left to right.

A contiguous rectangular subgrid of the mosaic matches the motif if every tile of the motif matches the color of the corresponding tile of the subgrid. Formally, an $r_p \times c_p$ motif appears in an $r_q \times c_q$ mosaic at position ($r$, $c$) if for all $1 \leq i \leq r_p$, $1 \leq j \leq c_p$, the tile ($r+i-1$, $c+j-1$) exists in the mosaic and either the square ($i$, $j$) in the motif is empty or the tile at ($i$, $j$) in the motif has the same color as the tile at ($r+i-1$, $c+j-1$) in the mosaic.

Given the full motif and mosaic, find all occurrences of the motif in the mosaic.

![](https://cdn.luogu.com.cn/upload/image_hosting/0n7urywk.png)

Figure G.1: Motif (left) and mosaic (right) of Sample Input 1.

inputFormat:
The first line of input contains two integers $r_p$ and $c_p$, where $r_p$ and $c_p$ ($1 \leq r_p, c_p \leq 1000$) are the number of rows and columns in the motif. Then $r_p$ lines follow, each with $c_p$ integers in the range $[0, 100]$, denoting the color of the motif at that position. A value of $0$ denotes an empty square.

The next line of input contains two integers $r_q$ and $c_q$ where $r_q$ and $c_q$ ($1 \leq r_q, c_q \leq 1000$) are the number of rows and columns in the mosaic. Then $r_q$ lines follow, each with $c_q$ integers in the range $[1, 100]$, denoting the color of the mosaic at that position.

outputFormat: On the first line, output $k$, the total number of matches. Then output $k$ lines, each of the form $r c$ where $r$ is the row and $c$ is the column of the top left tile of the match. Sort matches by increasing $r$, breaking ties by increasing $c$.

translation:
#### 简要题意
给出两个矩阵, 其中第二个矩阵所有元素非 $0$.

定义第一个矩阵在第二个矩阵中的坐标 $(l, r)$ 处「出现」, 当且仅当存在一种方式任意修改第一个矩阵所有为 $0$ 的元素后, 第一个矩阵的左上角在第二个矩阵的对应位置坐标为 $(l, r)$ 时可以与第二个矩阵的一部分完全重合.

求第一个矩阵在第二个矩阵中所有「出现」的位置和总「出现」次数。

#### 输入格式
第一行, 两个整数 $r_p, c_p$, 表示第一个矩阵的行数和列数.

接下来 $r_p$ 行, 每行 $c_p$ 个整数, 描述第一个矩阵.

接下来一行, 两个整数 $r_q, c_q$, 表示第二个矩阵的行数和列数.

接下来 $r_q$ 行，每行 $c_q$ 个整数, 描述第二个矩阵.

#### 输出格式
第一行, 一个整数 $k$, 表示「出现」的总次数.

接下来 $k$ 行, 每行两个整数 $x, y$, 表示每一次「出现」的坐标. 如果有多个, 请以 $x$ 为第一关键字, $y$ 为第二关键字升序排序后输出。


title: [ICPC2021 WF] Prehistoric Programs

description:
Archaeologists have discovered exciting clay tablets in deep layers of Alutila Cave. Nobody was able to decipher the script on the tablets, except for two symbols that seem to describe nested structures not unlike opening and closing parentheses in LISP. Could it be that humans wrote programs thousands of years ago?

Taken together, the tablets appear to describe a great piece of work $-$ perhaps a program, or an epic, or even tax records! Unsurprisingly, after such a long time, the tablets are in a state of disorder. Your job is to arrange them into a sequence so that the resulting work has a properly nested parenthesis structure. Considering only opening and closing parentheses, a properly nested structure is either

- $()$, or
- $(A)$, where $A$ is a properly nested structure, or
- $AB$, where $A$ and $B$ are properly nested structures.

inputFormat: The first line of input contains one integer $n$ ($1 \leq n \leq 10^6$), the number of tablets. Each of the remaining $n$ lines describes a tablet, and contains a non-empty string of opening and closing parentheses; symbols unrelated to the nesting structure are omitted. The strings are numbered from $1$ to $n$ in the order that they appear in the input. The input contains at most $10^7$ parentheses.

outputFormat: Output a permutation of the numbers from $1$ to $n$ such that concatenating the strings in this order results in a properly nested structure. If this happens for multiple permutations, any one of them will be accepted. If there is no such permutation, output $\texttt{impossible}$ instead.

translation:
给定 $n$ 个括号序列，要求以某个顺序排列这些序列后，连接起来，整个括号序是合法匹配的。输出连接顺序，无解输出 `impossible`。

translated by [liangbowen](https://www.luogu.com.cn/user/367488).


title: [ICPC2021 WF] Spider Walk

description:
Charlotte the spider sits at the center of her spiderweb, which consists of a series of silken straight strands that go from the center to the outer boundary of the web. Charlotte's web also has bridges, each of which connects two adjacent strands. The two endpoints of a bridge always have the same distance to the center of the spiderweb.

When Charlotte has finished a late-night feasting in the center and wants to retreat to some corner, she walks to the edge on autopilot. To do this, she picks a starting strand, and walks along it until she meets the first bridge on that strand. She will cross the bridge and go to the other strand, and then keeps walking outwards until she meets another bridge. Then she will cross that bridge, and repeat this process, until there are no more bridges on the current strand, and then she will walk to the end of the current strand. Note that Charlotte must cross all the bridges that she meets. Figure I.1 illustrates one path Charlotte could take.

Charlotte's favorite corner to sleep in during the daytime is at the end of strand $s$. For each possible starting strand, she wants to know the minimum number of bridges to add to the original web in order to end at $s$. Charlotte can add a bridge at any point along the strand, as long as the added bridge does not touch any other bridge. The two endpoints of any added bridge must have the same distance to the center of the spiderweb, and the bridge must connect two adjacent strands.

![](https://cdn.luogu.com.cn/upload/image_hosting/7nb4cy7c.png)

Figure I.1: The path starting from strand 4 on the spiderweb in Sample Input 1.

inputFormat: The first line of input has three integers $n$, $m$, and $s$, where $n$ ($3 \leq n \leq 200000$) is the number of strands, m ($0 \leq m \leq 500000$) is the number of bridges, and $s$ ($1 \leq s \leq n$) is Charlotte's favorite strand. Strands are labeled from $1$ to $n$ in counterclockwise order. Each of the remaining $m$ lines contains two integers $d$ and $t$ describing a bridge, where $d$ ($1 \leq d \leq 10^9$) is the bridge's distance from the center of the spiderweb and $t$ ($1 \leq t \leq n$) is the first strand of the bridge in counterclockwise order. Specifically, if $1 \leq t < n$, then the bridge connects strands $t$ and $t+1$. If $t = n$, then the bridge connects strands $1$ and $n$. All bridge distances $d$ are distinct.

outputFormat: Output $n$ lines, where the $i^{th}$ line is the minimum number of bridges Charlotte needs to add in order to end at strand $s$ after walking on autopilot from strand $i$.

translation:
有一个蜘蛛网，蜘蛛网包含一个中心点，从中心点放射出的 $n$ 条射线，按逆时针方向从 $1$ 到 $n$ 编号，以及 $m$ 条线段，称为“桥”，每条“桥”连接相邻的两条射线。每一条“桥”都和其连接的两条射线构成以中心点为顶点的等腰三角形。

现有一只蜘蛛从某一条射线的无穷远方向出发向中心点移动。如果在路上遇到了“桥” 的一个端点，蜘蛛会沿桥前往另一个端点到达另一条射线，然后继续往中心点移动。

现在蜘蛛会从 $1-n$ 号的每一条射线出发，并且希望最终经由 $s$ 号射线到达中心点。为了这一目的，可以在任两条射线之间的任意位置添加若干个“桥”。你需要对于 $1-n$ 的每一个出发位置计算最少添加“桥”的数量。注意各个询问之间是独立的，在一个询问中添加的“桥”不会对后续询问造成影响。

$3\le n\le200000$，$0\le n\le 500000$，$1\le s\le n$。


title: [ICPC2021 WF] Splitstream

description:
A splitstream system is an acyclic network of nodes that processes finite sequences of numbers. There are two types of nodes (illustrated in Figure J.1):

- A *split* node takes a sequence of numbers as input and distributes them alternatingly to its two outputs. The first number goes to output $1$, the second to output $2$, the third to output $1$, the fourth to output $2$, and so on, in this order.

- A *merge** node takes two sequences of numbers as input and merges them alternatingly to form its single output. The output contains the first number from input $1$, then the first from input $2$, then the second from input $1$, then the second from input $2$, and so on. If one of the input sequences is shorter than the other, then the remaining numbers from the longer sequence are simply transmitted without being merged after the shorter sequence has been exhausted.

 ![](https://cdn.luogu.com.cn/upload/image_hosting/e0gr6wa3.png)

  Figure J.1: Illustration of how split and merge nodes work.

The overall network has one input, which is the sequence of positive integers $1, 2, 3, \ldots, m$. Any output of any node can be queried. A query will seek to identify the $k^{th}$ number in the sequence of numbers for a given output and a given $k$. Your task is to implement such queries efficiently.

inputFormat:
The first line of input contains three integers $m$, $n$, and $q$, where $m$ ($1 \leq m \leq 10^9$) is the length of the input sequence, $n$ ($1 \leq n \leq 10^4$) is the number of nodes, and $q$ ($1 \leq q \leq 10^3$) is the number of queries.

The next $n$ lines describe the network, one node per line. A split node has the format $\texttt{S} \ x \ y \ z$, where $x$, $y$ and $z$ identify its input, first output and second output, respectively. A merge node has the format $\texttt{M} \ x \ y \ z$, where $x$, $y$ and $z$ identify its first input, second input and output, respectively. Identifiers $x$, $y$ and $z$ are distinct positive integers. The overall input is identified by $1$, and the remaining input/output identifiers form a consecutive sequence beginning at $2$. Every input identifier except $1$ appears as exactly one output. Every output identifier appears as the input of at most one node.

Each of the next $q$ lines describes a query. Each query consists of two integers $x$ and $k$, where $x$ ($2 \leq x \leq 10^5$) is a valid output identifier and $k$ ($1 \leq k \leq 10^9$) is the index of the desired number in that sequence. Indexing in a sequence starts with $1$.

outputFormat: For each query $x$ and $k$ output one line with the $k^{th}$ number in the output sequence identified by $x$, or $\texttt{none}$ if there is no element with that index number.

translation:
### 题意
有一个有 $n$ 个节点的传输数字序列的网络，其中有两种节点：拆分节点和合并节点。拆分节点会将输入序列中的数字交替插入两个输出序列中，合并节点会交替将两个输入序列中的数字插入输出序列中。例如：

$\{1,2,3,4,5\}$ 拆分得 $\{1,3,5\}$ 和 $\{2,4\}$。

$\{2,4\}$ 和 $\{1,3,5\}$ 合并得 $\{2,1,4,3,5\}$。

在网络中，除 $1$ 号外每一个结点的每一个输入端都连接着另一个节点的输出端,$1$ 号节点的输入端为总输入端，每一个输出端不一定连接着另一个节点的输入端。每一个输出端都有着从 $2$ 开始的正整数编号。

将一个数字序列 $\{1,2,\cdots,m\}$ 从 $1$ 号节点的输入端输入网络，你需要求出编号为  $x$ 的输出端输出的序列中的第 $k$ 个数字。

### 输入格式
第一行三个整数 $n,m,q$。分别表示结点的个数、输入序列为 $\{1,2,\cdots,m\}$、查询的次数。

接下来 $n$ 行，每行一个字母开头，接着是三个整数 $x,y,z$。若字母为 $S$，则表示这是一个拆分节点，$x$ 是它的输入端所连接的输出端编号，$y,z$ 是它的两个输出端的编号；若字母为 $M$，则表示这是一个合并节点，$x,y$ 是它的两个输入端所连接的输出端的编号，$z$ 是它的输出端编号。

再接下来 $q$ 行，每行两个整数 $x,k$，意义如题意中所述。

### 输出格式
对于每一次询问，输出其对应的回答。若答案不存在，输出 `none`。


title: [ICPC2021 WF] Take On Meme

description:
The Internet can be so fickle. You work for a small ad agency, Mimi's Mammoth Memes. Your ad campaigns are very cheap, and rely on the hope of producing the next hit viral meme. Unfortunately, the last four hundred or so memes have failed to take off, despite having been precisely engineered to appeal to every single person on Earth. You're not sure what exactly went wrong, but you've decided to try a new approach: crowd sourcing!

According to your scientific meme theory, all memes can be rated from $-\infty$ to $\infty$ on two scales: xanthochromism, and yellowishness, also known as ($x$, $y$) values. Obviously (you think), the best memes are memorable for being particularly xanthochromic, yellowish, unxanthochromic, or unyellowish. You feel that the "quality" of any meme is directly measurable as its squared Euclidean distance ($x^2 + y^2$) from the Base Meme ($0$, $0$), otherwise known as All Your Base.

To produce the ultimate viral meme, you'll be taking your company's last few failed memes and throwing them into a tournament, decided by online voting. The tournament can be represented as a rooted tree. Input memes come in at the leaves, and at each internal node, a vote will be held among its $k$ child memes ($x_1$, $y_1$), $\ldots$, ($x_k$, $y_k$). After the vote, all the memes will be horrifically mangled and merged into a brand new meme, specifically calculated to emphasize the winner and de-emphasize all the losers: the resultant $x$ value will be $$ \sum_{i=1}^{k} w_i \cdot x_i, $$ where $w_i$ is $1$ if the $i^{th}$ child won, and $-1$ otherwise. The $y$ value is computed similarly. This new meme will move on to the next vote in the tournament $-$ or, if there is no parent, it will be declared the champion and the ultimate meme!

You already have the structure of the tournament planned out, including all the input memes and the internal voting nodes. What is the largest possible quality for any meme that the tournament could produce?

inputFormat:
The first line of input contains an integer $n$ ($1 \leq n \leq 10^4$), giving the total number of nodes in the tournament tree. The next $n$ lines each describe a single tree node indexed from $1$ to $n$. The line for node $i$ starts with an integer $k_i$ ($0 \leq k_i \leq 100$), the number of children of that node. If $k_i$ is $0$, then node $i$ is an input meme and there will be two more integers $x_i$ and $y_i$ ($-10^3 \leq x_i, yi \leq 10^3$) describing it. If $k_i > 0$, then $k_i$ different integers $j$ ($i < j \leq n$) will follow, giving the indices of the $k_i$ nodes entering this voting step.

All input memes will eventually be merged into the final output meme at node $1$. The complete tree will have a height of no more than $10$.

outputFormat: Output the largest possible quality for the champion meme at node $1$.


title: [NEERC2017] Archery Tournament

description:
You were invited to the annual archery tournament. You are going to compete against the best archers from all of the Northern Eurasia. This year, a new type of competition is introduced, where a shooting range is dynamic and new targets might appear at any second.

As the shooting range is far enough from you, it can be represented as a 2D plane, where $y = 0$ is the ground level. There are some targets in a shape of a circle, and all the targets are standing on the ground. That means, if a target's center is $(x , y) (y > 0)$ , then its radius is equal to $y$ , so that it touches the line $y = 0$ . No two targets simultaneously present at the range at any given time intersect (but they may touch).

Initially, the shooting range is empty. Your participation in this competition can be described as $n$ events: either a new target appears at the range, or you shoot an arrow at some point at the range. To hit a target, you must shoot strictly inside the circle (hitting the border does not count). If you shoot and hit some target, then the target is removed from the range and you are awarded one point.

inputFormat:
The first line of the input contains integer $n (1 \le n \le 2·10^{5}).$ Next $n$ lines describe the events happening at the tournament. The i-th line contains three integers $t_{i}, x_{i},$ and $y_{i} (t_{i} = 1 , 2$ ; $−10^{9} \le x_{i}, y_{i} \le 10^{9}$ ; $y_{i} > 0)$ .

If $t_{i} = 1$ , then a new target with center $(x_{i}, y_{i})$ and radius $y_{i}$ appears at the range.

If $t_{i} = 2$ , then you perform a shot, which hits the range at $(x_{i}, y_{i}).$

outputFormat: For each of your shots, output a separate line with the single integer. If the shot did not hit any target, print `-1`. If the shot hit a target, print the number of event when that target was added to the range. Events are numbered starting from $1$ .

translation: 给出一些圆，这些圆圆心在 $x$ 轴上方，且与 $x$ 轴相切，任意时刻，不存在图上的圆相交，给出两种操作：增加一个圆；向图中发送一颗子弹，如果击中某个圆，输出该圆编号并且删掉这个圆。如果未击中，则输出 `-1`。

hint: Time limit: 3 s, Memory limit: 512 MB.


title: [NEERC2017] Box

description:
Bella is working in a factory that produces boxes. All boxes are in a shape of rectangular parallelepipeds. A net of the corresponding parallelepiped is cut out of a flat rectangular piece of cardboard of size $w$ *h . This net is a polygon with sides parallel to the sides of the rectangle of the cardboard. The net is bent along several lines and is connected along the edges of the resulting parallelepiped to form a box. The net is bent only along the edges of the resulting box.

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15284/1.png)

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15284/2.png)

The first example

The third example

Bella is a software developer and her task is to check whether it is possible to make a box of size $a \times b \times c$ out of a cardboard of size $w \times h$ . Bella did write a program and boxes are being produced. Can you do the same?

inputFormat:
The first line contains three integers a , $b$ , and $c$ -- the dimensions of the box.

The second line contains two integers $w$ and $h$ -- the width and the height of the cardboard.

All integers are positive and do not exceed $10^{8}.$

outputFormat: Print `Yes` if it is possible to cut a box a $ \times b \times c$ out of a cardboard of size $w \times h$ . Print `No` otherwise.

translation:
给出一个长方体的长、宽、高（分别是 $a, b, c$），问：能否在一张长为 $w$，宽为 $h$ 的纸上裁出这个长方体的某一个侧面展开图。

如果可以，请输出 `Yes`，否则输出 `No`。


title: [NEERC2017] Connections

description:
Hard times are coming to Byteland. Quantum computing is becoming mainstream and Qubitland is going to occupy Byteland. The main problem is that Byteland does not have enough money for this war, so the King of Byteland Byteman $0x0B$ had decided to reform its road system to reduce expenses.

Byteland has $n$ cities that are connected by $m$ one-way roads and it is possible to get from any city to any other city using these roads. No two roads intersect outside of the cities and no other roads exist. By the way, roads are one-way because every road has a halfway barrier that may be passed in one direction only. These barriers are intended to force enemies to waste their time if they choose the wrong way.

The idea of the upcoming road reform is to abandon some roads so that exactly $2n$ roads remain. Advisers of the King think that it should be enough to keep the ability to get from any city to any other city. (Maybe even less is enough? They do not know for sure. ) The problem is how to choose roads to abandon. Everyone in Byteland knows that you are the only one who can solve this problem.

inputFormat:
Input consists of several test cases. The first line of the input contains the number of tests cases.

The first line of each test case contains $n$ and $m$ -- the number of cities and the number of roads correspondingly $(n \ge 4 , m > 2n).$ Each of the next $m$ lines contains two numbers $x_i$ and $y_i$ denoting a road from city $x_{i}$ to city $y_{i} (1 \le x_{i}, y_{i} \le n , x_{i} ≠ y_{i}).$ It is guaranteed that it is possible to get from any city to any other city using existing roads only. For each pair $(x , y)$ of cities there is at most one road going from city $x$ to city $y$ and at most one road going from city $y$ to city $x$ . The solution is guaranteed to exist. The sum of $m$ over all test cases in a single input does not exceed $100 000$ .

outputFormat: For each test case output $m − 2n$ lines. Each line describes a road that should be abandoned. Print the road in the same format as in the input: the number of the source city and the number of the destination city. The order of roads in the output does not matter, but each road from the input may appear in the output at most once and each road in the output must have been in the input. It still must be possible to get from any city to any other city using the remaining roads.

translation: 给定一个 $n$ 点有向图，要求保留 $2n$ 条边使得强连通关系不变，输出删去的边


title: [NEERC2017] Designing the Toy

description:
You are the main toy producer in the city. Recently you bought a $3D-printer$ that provides you with an unprecedented opportunity for designing new fancy toys for children.

In a package with the $3D-printer$ there is a booklet containing several examples of what can be created with it. One of the examples is a figure that looks like a triangle, like a circle, or like a square depending on which of its sides you are looking at.

Unfortunately, it turned out that the booklet describes the most recent version of your printer. Your printer is only able to create figures that consist of voxels (three-dimensional pixels), i.e . figures that look like a union of a unit-length cubes that are the cells of a three-dimensional grid. Thus, you are not able to print any `smooth` figures (like a sphere, for example) with it. On the other hand, important feature of your model is its ability to create figures whose parts are not even connected with each other by putting wires of a negligible thickness between them.

You like the idea of the figure in the booklet, so you decided to improve upon this idea. Instead of specifying shapes of figure projections from different perspectives, you would specify their areas. In this problem, a voxel is defined by a triple of integers $(x , y , z)$ , which corresponds to a unit cube [x , $x + 1] \times $ [y , $y + 1] \times $ [z , $z + 1].$

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15286/1.png)

You are given three positive integers a , $b$ and $c$ . Your task is to find a description of a figure $F$ consisting of one or more voxels, for which the area of its orthogonal projection onto the plane Oxy is a , the area of its orthogonal projection onto the plane Oxz is $b$ , and the area of its orthogonal projection onto the plane Oyz is $c$ , or to determine that it is impossible.

inputFormat: The only line of the input contains three integers a , $b$ , and $c (1 \le $ a , $b , c \le 100)$ -- the desired area of orthogonal projections onto the planes Oxy, Oxz, and Oyz correspondingly.

outputFormat:
If it is impossible to find the desired figure, print only the integer $−1$ .

Otherwise, in the first line print the integer $n$ , defining the number of voxels in the figure. Then print $n$ triples $x , y , z (−100 \le x , y , z \le 100)$ defining the voxels of the figure. Voxels may be printed in any order, but no voxel may be repeated twice.

The number of voxels $n$ should not exceed $10^{6}.$

Any figure with the requested projection areas is accepted.

translation:
## 题目描述

你是这里的玩具生产大佬。最近你买了一台 3D 打印机，它给你提供了一个~~大赚一笔~~创造新玩具的机会。

你的打印机只能打印由一个个单位方块（棱长为 $1$ 的正方体）构成的几何体。因此，你不能打印出任何“光滑”的几何体（比如球体）。另外，这台打印机打印的几何体可以有完全不相连甚至浮空的部分。

建立空间直角坐标系。一个 $[x , x + 1] $ $\times $ $[y , y + 1]$ $\times $ $[z , z + 1]$ 的方块用整数三元组 $(x , y , z)$ 表示。

现在你想指定打印出的几何体在平面 $Oxy$，平面 $Oxz$ 和平面 $Oyz$ 上的投影面积。

![](https://cdn.luogu.com.cn/upload/image_hosting/udemly1h.png)

给出三个正整数 $a,b,c$，依次表示几何体在平面 $Oxy$，平面 $Oxz$ 和平面 $Oyz$ 上的投影面积。判断该集合体是否存在，若存在，找到满足条件的几何体。

## 输入格式

一行，包含 $3$ 个正整数 $a,b,c$ $(1 \le a , b , c \le 100)$。

## 输出格式

如果所求几何体不存在，输出 `-1` 。

否则，输出的第一行包含一个整数 $n$，表示图中方块的数量。

接下来 $n$ 行，每行 $3$ 个整数 $x,y,z$ 表示每个方块的位置。方块可以按任意顺序输出，但不能重复。

$n$ 的值不应超过 $10^{6}$。

任何满足条件的几何体都算作正确。

## 提示

时间限制：3s，内存限制：512MB。

Translated by Georiky


title: [NEERC2017] Easy Quest

description:
A young hero is starting his heroic life. The wise wizard suggested him an easy first quest. During this quest our young hero meets $n$ magical creatures, in specific order. In order to help the young hero, the wizard gave him a clue -- a list of $n$ integers $a_{i}.$

If $a_{i}$ is positive, then the i-th magical creature is benevolent and gives to our hero one magical item of type $a_{i}.$ The hero can keep several items of the same type.

If $a_i$ is negative, then the i-th magical creature is evil and in order to defeat it the young hero needs one magical item of type $−a_{i}.$ All magical items are fragile and can be used only once.

If $a_{i}$ is zero, then the i-th creature is a unicorn. It gives the hero any magical item he asks for, but only one.

Your task is to help the young hero to finish the first quest, defeating all enemies on the way, or say that it is impossible.

inputFormat: The first line of input contains one integer $n (1 \le n \le 1000)$ . The second line contains $n$ integers $a_{i} (−1000 \le a_{i} \le 1000)$ .

outputFormat: If it is impossible to defeat all enemies, then output one string `No`. If it is possible, then output string `Yes`, and in the next line output the types of items the hero should ask the unicorns for, in order they meet during the quest. Types must be integers in range from $1$ to $1000$ inclusive. If there are several solutions, output any of them.

translation:
一个英雄进行了一次探索。在这次探索中，英雄按特定顺序遇到了 $n$ 个魔法生物，第 $i$ 个魔法生物对应 $a_i$。

当 $a_i$ 为正数时，第 $i$ 个魔法生物会给英雄提供一个为 $a_i$ 的魔法物品。

当 $a_i$ 为负数时，第 $i$ 个魔法生物需要英雄消耗一个为 $-a_i$ 的魔法物品。

当 $a_i$ 为 $0$ 时，第 $i$ 个魔法生物可以给英雄提供一个任意的魔法物品。

你需要回答英雄是否可以完成这次探索（经过所有魔法生物），如果可以，请回答 $a_i$ 为 $0$ 魔法生物应该为英雄提供哪种魔法物品。

hint:
Time limit: 3 s, Memory limit: 512 MB.

spj provider:@[shenyouran](/user/137367).


title: [NEERC2017] The Final Level

description:
Fiora is a game designer. Now she is designing the final level for her new game.

A level for this game is a labyrinth on a rectangular grid with lots of enemies. Player starts her game at the square $(0 , 0)$ and her purpose is to get to the square $(a , b)$ . Fiora has lots of ideas on how to put enemies, but she does not like designing labyrinths. She needs your help here.

Fiora is drawing levels in a special level editor which supports one basic block to design a labyrinth. This block is an L-shaped corner, consisting of two perpendicular rectangles $1 \times n$ squares in size intersecting at $1 \times 1$ square. It is possible to rotate this block in four ways. Blocks cannot intersect, but they can touch each other. Player can move through all the squares lying in any block. She can move between two squares if they are sharing a side, even if they are in different blocks.

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15288/1.png)

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15288/2.png)

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/15288/3.png)

Blocks with $n = 3$

The first example

The second example

Fiora wants to design the final level with the minimal possible number of blocks. Of course, it should be possible to move from square $(0 , 0)$ to square $(a , b)$ .

inputFormat: The first line of the input consists of a single integer $m (1 \le m \le 100)$ -- the number of test cases. It is followed by $m$ test cases. Each test case is on a separate line and consists of three integers a , $b$ , and $n (−10^{8} \le $ a , $b \le 10^{8}; 2 \le n \le 10^{8})$ -- a is the coordinate of the final point along the horizontal axis, $b$ is the coordinate of the final point along the vertical axis, and $n$ is the size of the block. The final point is not same as the starting one (either a $≠ 0$ or $b ≠ 0)$ .

outputFormat:
For each test case, in the first line print the minimal number $k$ of blocks you need. In the following $k$ lines print description of these blocks. Each L-shaped corner block is described by coordinates of two cells. Print coordinates of the end of its vertical rectangle, followed by coordinates of the end of its horizontal rectangle. Specify the coordinates of the ends that are opposite to the intersection of the rectangles. Note that the order of cells in the block description matters, since a change of the order results in a reflected block. Coordinates of each end should be printed with the coordinate along the horizontal axis first, followed by the coordinate along the vertical axis.

All coordinates in the output should not exceed $10^{9}$ by absolute value.

It is guaranteed that the total number of blocks in the correct output does not exceed $10^{5}$ for all test cases combined.

translation:
用长度为 $n$ 的 L 型方块摆在二维网格平面上，仅通过方块从 $(0,0)$ 走到 $(a,b)$。

### 输入格式

第一行一个正整数 $m$ ，下面 $m$ 行每行 $3$ 个正整数 $a, b, n$。

### 输出格式

对于每组数据，输出最小 L 型块数 $k$，下面 $k$ 行每行按先横坐标后纵坐标的顺序输出每个 L 型块两端的坐标。

### 数据范围

对于 $100\%$ 的数据，$1 \le m \le 100, -10^8 \le a, b  \le 10^8, 2 \le n \le 10^8$。


title: [NEERC2017] The Great Wall

description:
Recently you had become an emperor of a small country of Sinai. You had decided to build a big wall at the border to save your country from barbarian raids. You had contacted `W Corp`, the only company in the world that builds non-penetrable walls.

`W Corp` builds each wall using the same pattern. The length of the wall is $n$ meters. Each one-meter piece of the wall is numbered by an integer from $1$ to $n$ along its length and may have a different height. The height pattern is based on three fixed arrays a , $b$ , and $c$ of $n$ elements each, such that $a_{i} < b_{i} < c_{i}$ for all $1 \le i \le n$ , and an integer $r (1 \le r < n)$ . These arrays and $r$ are the same for any wall that is built by `W Corp`.

The choice of the specific wall design is determined by two distinct integers $x$ and $y (1 \le x < y \le n−r+1)$ in the following way. Take two ranges of integers: [x , $x+r−1]$ and [y , $y+r−1]$ (these ranges are inclusive of their ends). Then the height of the wall at one meter piece $i$ for all $1 \le i \le n$ is equal to:

$a_{i}$ if $i$ does not belong to any of the chosen ranges;

$b_{i}$ if $i$ belongs to exactly one chosen range;

$c_{i}$ if $i$ belongs to both chosen ranges.

A strength of a wall is defined as the sum of all heights of its $n$ one meter pieces.

The arrays a , $b , c$ , and an integer $r$ are the same for any wall built by `W Corp`, so the company provides a price list with all the possible wall designs, sorted in non-decreasing order of their strength. You choose the k-th wall design from the list. The task is to find the strength of the chosen wall.

inputFormat:
The first line of the input contains three integers $n , r$ and $k (2 \le n \le 30 000 , 1 \le r < n , 1 \le k \le (n−r)(n−r+1)/2)$ -- the length of the wall, the length of the segments to choose, and the position of the wall in the price list.

The second line of the input contains the elements of the array a $(1 \le a_{i} \le 10^{6}).$

The third line of the input contains the elements of the array $b (a_{i} < b_{i} \le 10^{6}).$

The fourth line of the input contains the elements of the array $c (b_{i} < c_{i} \le 10^{6}).$

outputFormat: Print one integer -- the strength of the k-th wall from `W Corp` price list.

translation:
最近你成为了西奈一个小国家的皇帝。你决定在边界建造一座长城保护你的国家不被野蛮人抢劫。你联系了“W Corp”——世界上唯一的建造坚不可摧的墙的公司。

“W Corp”用相同的格式建造所有墙。墙的长度是 $n$ 米，每一米墙按顺序从 $1$ 到 $n$ 编号，它们可能有不同的高度。高度的格式取决于三个固定的数组 $a,b,c$，它们各有 $n$ 个元素，对于任意 $1\le i\le n$ 满足 $a_i < b_i < c_i$，还有一个整数 $r\ (1\le r < n)$。三个数组和 $r$ 对于“W Corp”建造的任何墙都是相同的。

按照如下方式，具体的墙体设计的选择取决于两个不同的整数 $x,y\ (1\le x < y\le n-r+1)$。取两个整数区间：$[x,x+r-1]$ 和 $[y,y+r-1]$（区间包括端点）。那么第 $i$ 米墙的高度是：

- $a_i$，当 $i$ 不属于这两个区间
- $b_i$，当 $i$ 属于这两个区间中的恰好一个
- $c_i$，当 $i$ 属于这两个区间中的两个

墙的**强度**定义为每一米墙高度的和。

在“W Corp”建造的所有墙中，数组 $a,b,c$ 和整数 $r$ 都是固定的。公司提供了一份所有可能的墙体设计的列表，按照强度单调不减排序。你选择了其中第 $k$ 种墙体设计。你的任务是，求出你选择的墙的强度。

### 输入格式

第一行包括三个整数 $n,r,k\ (2\le n\le 30000,\ 1\le r < n,\ 1\le k\le \frac{(n-r)(n-r+1)}{2}\ \ )$，分别代表墙的长度，取的区间的长度，你的选择在列表中的位置。

第二行包括了数组 $a$ 的元素，$1\le a_i\le 10^6$。

第三行包括了数组 $b$ 的元素，$1\le b_i\le 10^6$。

第四行包括了数组 $c$ 的元素，$1\le c_i\le 10^6$。

### 输出格式

输出一个整数，“W Corp”的列表中第 $k$ 种墙的强度

### 样例解释

在样例中，能建造出的不同的墙有三种：

- 选择 $x=1,y=2$，墙的高度是 $[3,7,5,4]$，强度是 $19$。
- 选择 $x=1,y=3$，墙的高度是 $[3,3,5,5]$，强度是 $16$。
- 选择 $x=2,y=3$，墙的高度是 $[1,3,7,5]$，强度是 $16$。


title: [NEERC2017] Interactive Sort

background: 这是一道 IO 交互题。

description:
Ivan wants to play a game with you. He took all integers from $1$ to $n$ inclusive, shuffled them and then put all even numbers into array $e$ and all odd numbers into array $o$ .

Your task is to find arrays $e$ and $o$ .

You can ask Ivan questions of certain kind. Each question consists of two integers $i$ and $j$ . For each question Ivan says whether $e[i] < o[j]$ or not.

You can ask at most $300 000$ questions.

# Interaction Protocol

First, the testing system writes the integer $n (1 \le n \le 10 000)$ -- the number of integers Ivan used.

Your solution shall print requests of two types:

• “? i j”. $1 \le i \le ⌊n/2⌋, 1 \le j \le ⌈n/2⌉$. The testing system responds with the symbol $“<”$ if $e[i] < o[j]$ or with the symbol $“>”$ otherwise.

• “!\ $e_1\ e_2\ \cdots e_{⌊n/2⌋}\ o_1\ o_2 \cdots o_{⌈n/2⌉}$” tells the values of $e$ and $o$ that your program has determined.

Don't forget to flush the output after each request!

Your solution must issue exactly one request of the second type, which must be the last request, and thesolution must terminate gracefully after issuing it.

Your solution is allowed to issue at most $300 000$ requests of the first type.

For each test case the number $n$ is fixed and the numbers are shuffled using Java built-in shuffle functionwith fixed seed.

translation:
有一个长度为 $n(n\le 10000)$ 的排列，所有奇数组成的序列设为 $o$，所有偶数组成的序列设为 $e$。

你可以进行不超过 $300000$ 次询问 `? i j`，每次交互库会返回一个 `<` 或 `>` 表示 $e_i$ 和 $o_j$ 的大小关系，最后你需要求出 $e,o$ 并输出，格式为 `! e o`。

保证数据随机。


title: [NEERC2017] Hack

description:
Heidi is analyzing a peculiar device. This device takes an a as input and computes $a^d(mod n)$ using thefollowing pseudocode and some integers $d$ and $n$ stored in this device:

 ```
modPow(a, d, n) {
  r = 1;
  for (i = 0; i < 60; ++i) {
    if ((d & (1 << i)) != 0) {
      r = r * a % n;
    }
  a = a * a % n;
  }
}
```

Note that the pseudocode assumes arbitrary sized integers, $<<$ denotes bitwise shift left, $&$ denotes bitwise

and, and % denotes modulo.

The device does not tell Heidi the result of the computation. However, Heidi can measure how long does the computation take. She knows that only multiplication modulo $n$ (lines $5$ and $7$ in the above pseudocode) takes any measurable amount of time, all other lines can be assumed to take $0$ nanoseconds.

Moreover, she knows that it takes $(bits(x) + 1) · (bits(y) + 1)$ nanoseconds to multiply $x$ by $y$ modulo $n$ , where $bits(x)$ is the number of bits in the binary representation of $x$ without leading zeros, or more formally $\text{bits(x)} = ⌈\log_2 (x + 1)⌉.

Heidi knows the integer $n$ but does not know the integer $d$ . She wants to find $d$ by feeding the device different integers a as input and measuring the time the computation takes for each a .

She knows that $n$ and $d$ were chosen in the following way: first, two prime numbers $p$ and $q$ with $30$ bits in binary representation (in other words, between $229$ and $230 −1)$ were picked independently and uniformly at random. Then the number $n$ was computed as $n = p · q$ . Then the number $m = φ(n) = (p−1)·(q −1)$

was computed. Then $d$ was picked uniformly at random between $1$ and $m − 1$ inclusive, such that it is coprime with $m$ .

# Interaction Protocol

First, the testing system writes the integer $n$ -- the modulo used by the device. Note that $n$ and the hidden number $d$ are guaranteed to have been generated according to the procedure described above.

Your solution shall print requests of two types:

- “? a” tells to feed a as input to the device. a must be an integer between $0$ and $n−1$ inclusive. The testing system responds with the time it took the device to compute `modPow(a , d , n)` in nanoseconds.

- “! d” tells the value of $d$ that your program has determined.

Don't forget to flush the output after each request!

Your solution must issue exactly one request of the second type, which must be the last request, and the solution must terminate gracefully after issuing it.

Your solution is allowed to issue at most $30 000$ requests of the first type.

Your solution will be run on $30$ testcases, working with one $(n , d)$ pair per run. For each testcase the numbers $n$ and $d$ are fixed and were generated using the procedure described above. The example below

was not generated in that manner and thus will not be used for testing your solution; it only serves to illustrate the input/output format and provide a sanity check for your calculation of the computation time.

translation:
有如下的一个程序来计算 $a^d(mod \ n)$，（$d,n$是常数）

```cpp
modPow(a, d, n) {
	r = 1;
 	for (i = 0; i < 60; ++i) {
   		if ((d & (1 << i)) != 0) {
     		r = r * a % n;
   		}
 		a = a * a % n;
 	}
}
```

其中，计算 $x * y\ \  mod \ n$ （上述伪代码中的第 $5$ 行和第 $7$ 行）需要消耗 $(bits(x) + 1)* (bits(y) + 1)$ 纳秒，$bits(x)$ 是 $x$ 的二进制表示中不带前导零的位数，更正式的说，为 $\lceil \log_2(x+1) \rceil$，其他指令可以认为不需要任何时间。

你知道 $n$ ，但不知道 $d$， 你可以通过不超过 $30000$ 次询问对于 $a$ 计算 $a^d(mod \ n)$ 所用纳秒数。

正式数据中，$n,d$ 的生成方式如下：随机挑选两个 $[2^{29},2^{30}-1]$ 的质数 $p,q$，$n=pq$，而 $d$ 为在 $[1,\varphi(n)]$ 随机挑选的，与 $\varphi(n)=(p-1)*(q-1)$ 互质的数

**这是一道交互题**

首先，将给出整数 $n$

有两种指令可用：

“? a”询问对于正整数 $a$ 计算 $a^d(mod \ n)$ 所用纳秒数。要求$a<n$。返回所用的纳秒数

“! d”表示确定了 $d$ 的值并提交，你的程序应当在此后结束。


title: [NEERC2017] Journey from Petersburg to Moscow

description:
To conduct The World Programming Cup $2112$ a network of wonderful toll roads was build in European part of Russia. This network consists of $m$ bidirectional roads that connect $n$ cities. Each road connects exactly two distinct cities, no two roads connect the same pair of cities, and it is possible to travel from any city to any other city using only this road network. Moreover, to ease the process of charging, no two roads intersect outside of the cities.

Each road is assigned some individual positive cost. Normally, if a driver makes a trip using some of these toll roads, at the end of his journey he would be charged the total cost equal to the sum of individual costs of all roads he has used. To increase the popularity of car travels between two capitals, the operator company Radishchev Inc introduced a special offer: make a journey from Saint Petersburg to Moscow and pay for only $k$ most expensive roads along your path.

Formally, let some path consists of $l$ roads. Denote as $c_{1}$ the cost of the most expensive road along this path, as $c_{2}$ the second most expensive and so on. Thus, we have a sequence $c_{1} \ge c_{2} \ge c_{3} \ge $ . . . $ \ge c_{l}$ of individual costs of all roads along the chosen path. If $l \le k$ , then the path is too short and the driver pays the sum of all individual costs as usual, i.e . $Σ^{l}_{i=1}c_{i}.$ If $l > k$ , then the driver only pays for $k$ most expensive roads, that is $Σ^{k}_{i=1}c_{i}.$

As the chief analyst of Radishchev Inc you were assigned a task to compute the cheapest possible journey from Saint Petersburg to Moscow.

inputFormat:
The first line of the input contains three integers $n , m$ and $k (2 \le n \le 3000 , 1 \le m \le 3000 , 1 \le k < n)$ -- the number of cities, the number of roads in the road network, and the maximum number of roads that one should pay for in a single journey.

Next $m$ lines contain description of roads. Each road description contains three integers $u_{i}, v_{i},$ and $w_{i} (1 \le u_{i}, v_{i} \le n , u_{i} ≠ v_{i}, 1 \le w_{i} \le 10^{9})$ -- the i-th bidirectional road that connects cities $u_{i}$ and $v_{i}$ with the cost of $w_{i}$ for any direction. It is guaranteed that there is at most one road between each pair of cities and it is possible to get from any city to any other city using only these roads.

outputFormat: Print one integer equal to the minimum possible cost of travel from the city number $1$ (Saint Petersburg) to the city number $n (Moscow).$

translation:
有 $n$ 座城市 $m$ 条道路，每条道路连接两座城市，每条道路都需要过路费。

$\mathsf{\color{black}{K}\color{red}{arry5307}}$ 想从城市 $1$ 出发前往城市 $n$。根据相关法律法规，对于一条经过 $c$ 条边的路径，$\mathsf{\color{black}{K}\color{red}{arry5307}}$ 只需要支付路径上前 $k$ 大的过路费（当 $c<k$ 时需要支付路径上全部的过路费）。

现在 $\mathsf{\color{black}{K}\color{red}{arry5307}}$ 想要求出从 $1$ 到达 $n$ 的最小花费。因为 $\mathsf{\color{black}{K}\color{red}{arry5307}}$ 忙着写神仙题，所以这个任务交给了你。

$2\leq n\leq 3000,1\leq m\leq 3000,1\leq k<n$。


title: [NEERC2017] Knapsack Cryptosystem

description:
The Merkle-Hellman Knapsack Cryptosystem was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in $1978$ . Here is its description

Alice chooses $n$ positive integers ${a_{1}, . . . , a_{n}}$ such that each $a_{i} > \sum^{i−1}_{j=1}a_{j},$ a positive integer $q$ which is greater than the sum of all $a_{i},$ and a positive integer $r$ which is coprime with $q$ . These $n + 2$ integers are Alice's private key.

Then Alice calculates $b_i = (a_{i} · r)$ mod $q$ . These $n$ integers are Alice's public key.

Knowing her public key, Bob can transmit a message of $n$ bits to Alice. To do that he calculates $s$ , the sum of $b_{i}$ with indices $i$ such that his message has bit $1$ in i-th position. This value $s$ is the encrypted message.

Note that an eavesdropper Eve, who knows the encrypted message and the public key, has to solve a (presumably hard) instance of the knapsack problem to find the original message. Meanwhile, after receiving $s$ , Alice can calculate the original message in linear time; we leave it to you as an exercise.

In this problem you deal with the implementation of the Merkle-Hellman Knapsack Cryptosystem in which Alice chose $q = 2^{64},$ for obvious performance reasons, and published this information. Since everyone knows her $q$ , she asks Bob to send her the calculated value $s$ taken modulo $2^{64}$ for simplicity of communication.

You are to break this implementation. Given the public key and an encrypted message, restore the original message.

inputFormat:
The first line contains one integer $n (1 \le n \le 64)$ .

Each of the next $n$ lines contains one integer $b_{i} (1 \le b_{i} < 2^{64}).$

The last line contains one integer $s$ mod $q$ -- the encrypted message $s$ taken modulo $q (0 \le s$ mod $q < 2^{64}).$

The given sequence $b_{i}$ is a valid public key in the described implementation, and the given value $s$ mod $q$ is a valid encrypted message.

outputFormat: Output exactly $n$ bits ($0$ or $1$ digits) -- the original message.

translation:
背包密码是一个简单的公钥密码系统，下面是它的具体过程：

- Alice 选择 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，满足 $a_i> \sum\limits_{j=1}^{i-1} a_j$，再选择两个正整数 $q,r$，满足 $q> \sum\limits_{j=1}^n a_i$，$r,q$ 互质。这 $n + 2$ 个数是 Alice 的私钥。再计算 $b_i = (a_i\cdot r)\bmod q$，这 $n+2$ 个数是 Alice 的公钥。

- Bob 有一个 01 串 $t$，他知道 Alice 的公钥，$t$ 加密后得到 $s=\left(\sum\limits_{i=1}^n [t_i=1]b_i\right)\bmod q$. 他把这个 01 串加密后的结果发给了 Alice。那 Alice 就可以在线性时间内解出来。

你现在截获了 $s$，并知道 $b_i$ 和 $q$，其中 $q = 2^{64}$。请解出这个 01 串。

$n\le 64$，保证 $s,b_i$ 合法。


title: [NEERC2017] Laminar Family

description:
While studying combinatorial optimization, Lucas came across the notion of `laminar set family`. A subset family $F$ of some set $Ω$ is called laminar if and only if it does not contain an empty set and for any two distinct sets A , $B ∈ F$ it is correct that either $A ⊂ B$ or $B ⊂ A$ or $A ∩ B = ∅$.

As an experienced problem setter Lucas always tries to apply each new piece of knowledge he gets as an idea for a programming competition problem. An area of his scientific interests covers recognition problems that usually sound like `Given some weird combinatorial property, check if the given structure satisfies it`.

Lucas believes that the perfect programming competition problem should contain a cactus a tree in it. Trying to put together laminar sets and trees into a recognition problem, he finally came up with the following problem: given an undirected tree on $n$ vertices and a family $F = {F_{1}, . . . , F_{k}}$ of sets, where $F_{i}$ consists of all vertices belonging to the simple path between some two vertices $a_{i}$ and $b_{i}$ of the tree, check if the family $F$ is a laminar family. Note that in this case $Ω = V$ , and each $F_{i} ⊆ V$ .

As you can see, Lucas had succeeded in suggesting this problem to the programming contest. Now it is up to you to solve it.

inputFormat:
The first line of the input contains two integers $n$ and $f (1 \le n , f \le 100 000)$ -- the number of vertices in the tree and the number of elements in a family $F$ .

Next $n−1$ lines describe the tree structure. In the i-th line there are two integers $u_{i}$ and $v_{i} (1 \le u_{i}, v_{i} \le n , u_{i} ≠ v_{i})$ -- the indices of the vertices that are connected by the i-th edge of the tree.

Next $f$ lines describe the sets forming the family $F$ . In the i-th line there are two integers $a_{i}$ and $b_{i} (1 \le a_{i}, b_{i} \le n)$ , such that $F_{i}$ consists of all vertices belonging to the simple path between vertices $a_{i}$ and $b_{i}$ in the tree (including $a_{i}$ and $b_{i}).$

outputFormat: Output the only word `Yes` or `No` depending on whether or not the given set family is laminar.

translation:
- 给定一棵 $n$ 个节点的树，给出 $f$ 条树上的路径，试判断下面的命题是否成立：
- $f$ 条路径中，任意两条路径的点集的交集为空，或者一个是另一个的子集。
- 成立输出 `Yes`，不成立输出 `No`。
- $1 \leq n,f \leq 10^5$

hint: Time limit: 2 s, Memory limit: 512 MB.


title: [NEERC2016] Abbreviation

description:
An abbreviation (from Latin brevis, meaning short) is a shortened form of a word or phrase. In this problem you must write an automated tool that replaces a sequence of capitalized words with the corresponding abbreviation that consists of the first upper case letters only, followed by a full definition in parenthesis. See sample input and output.

Let us make some formal definitions. A word in a text is a maximally long sequence of lower and upper case English letters. A capitalized word is a word that consists of an upper case letter followed by one or more lower case letters. For example, `Ab`, `Abc`, `Abcd`, and `Abcde` are all capitalized words, while `ab`, `A`, `AB`, `ABc` and `AbC` are not.

An abbreviatable sequence of words is a sequence of two or more capitalized words that are separated by exactly one space, no line breaks or punctuation are allowed inside it.

An abbreviation of an abbreviatable sequence of words is a sequence of the first (upper case) letters of each word, followed by a single space, an opening parenthesis, the original abbreviatable sequence, and a closing parenthesis.

inputFormat: The input file consists of up to $1 000$ lines of text with up to $120$ characters on each line. Each line consists of spaces, upper and lower case letters, commas or dots. There are no leading or trailing spaces on lines and there are no empty lines. There is at least one line in the input file.

outputFormat: Write to the output file the original text with every abbreviatable sequence of words replaced with the corresponding abbreviation.

translation:
### 题目描述
定义 word 为一个首字母大写、长度大于 1 、 其他位为小写字母的单词，如 `Ab`、 `Abc`、 `Abcd`、 和 `Abcde`，但 `ab`、`A`、 `AB`、 `ABc` 和 `AbC`。

定义一个 word 串为一个有大于 1 个 word 、每两个 word 中有且只有一个空格的串，如 `International Business Machines`。

现给你若干行，如遇到 word 串则让他变为缩写，缩写方式为：先提取首字母（大写），再加空格和 `(` ，再把全称写出来，最后加上 `)` ，如: `International Business Machines` 可缩写为 `IBM (International Business Machines)` 。

### 输入格式
若干行（不超过 1000 行）由大小写字母、标点和空格组成的的字符串（每行不超过 120 个字符）。

### 输出格式
缩写后的若干行字符串（无法缩写的不用缩写）。

#### translate by:`ddgtang`

samples:
This is ACM North Eastern European Regional Contest,
sponsored by International Business Machines.
The. Best. Contest. Ever.
A Great Opportunity for all contestants.

samples:
This is ACM NEERC (North Eastern European Regional Contest),
sponsored by IBM (International Business Machines).
The. Best. Contest. Ever.
A GO (Great Opportunity) for all contestants.

samples:
ab Ab A Abc AB Abcd ABc Abcde AbC
ab Ab A Abc AB Abcd ABc Abcde AbC

samples: Oh  No  Extra Spaces.And,Punctuation Ruin Everything

samples: Oh  No  ES (Extra Spaces).And,PRE (Punctuation Ruin Everything)

hint: Time limit: 1 s, Memory limit: 512 MB.


title: [NEERC2016] Binary Code

description:
Ben has recently learned about binary prefix codes. A binary code is a set of $n$ distinct nonempty code words $s_{i}$ , each consisting of 0s and $1s.$ A code is called a prefix code if for every $i ≠ j$ neither $s_{i}$ is a prefix of $s_{j}$ nor $s_{j}$ is a prefix of $s_{i}$ . A word $x$ is called a prefix of a word $w$ if there exists a possibly empty word $y$ , such that xy $= w$ . For example, $x = 11$ is a prefix of $w = 110$ and $x = 0100$ is a prefix of $w = 0100$ .

Ben found a paper with $n$ lines of binary code in it. However, this paper is pretty old and there are some unreadable characters. Fortunately, each word contains at most one unreadable character.

Ben wants to know whether these $n$ lines could represent a binary prefix code. In other words, can he replace every unreadable character with $0$ or $1$ , so that the code becomes a prefix code?

inputFormat:
The first line contains integer $n$ -- the number of code words $(1 \le n \le 5 · 10^{5}).$

Next $n$ lines contain nonempty code word records, one per line. Each code word record consists of `0`, `1` and `?` characters. Every code word record contains at most one `?` character that represents unreadable character.

The total length of words does not exceed $5 · 10^{5}$ .

outputFormat:
Output `NO` in the first line if the code cannot be a prefix code.

Otherwise, output `YES` in the first line. Next $n$ lines shall contain code words in the same order as the corresponding code word records in the input.

If there are several prefix codes, that could have been written on the paper, output any one.

translation:
### 题目描述

给定 `n` 个01串，每个字符串至多有一位是未知的，可以填 `0` 或 `1` ，求是否存在一种方案，使得任意一个字符串不是其它任意一个字符串的前缀

### 输入格式

第一行是一个正整数 `n` ，代表字符串的数量。 $(1 \leq n \leq 5 \cdot 10^5)$

接下来 `n` 行每行一个字符串，只可能由 `0` 、 `1` 或 `?` 组成。 `?` 代表未知的位置，每个字符串最多一个。

保证字符串总长度不超过 $5 \cdot 10^5$ 。

### 输出格式

如果无解，只需要输出 `NO` 。

如果有解，在第一行输出 `YES` ，接下来 `n` 行输出方案。

如果有多组解，只需要输出任意一组。

hint: Time limit: 2 s, Memory limit: 2048 MB.


title: [NEERC2016] Cactus Construction

description:
Let us consider the following way of constructing graphs. Pick the number of colors $ˆc$ . Let $n$ be the number of vertices in a graph. To build a graph, we use a workspace with several graphs in it. Each vertex of each graph has a color. Colors are denoted by integers from $1$ to $ˆc$ . Initially, we have $n$ graphs in a workspace with one vertex in each graph, all colored with color $1$ , and no edges. The only vertex of i-th graph has number $i$ .

The following operations are permitted:

join a $b$ : join graphs containing vertices a and $b$ into one graph. No edges are added. Vertices a and $b$ must be in different graphs.

recolor a $c_{1 }c_{2}:$ in graph containing vertex a recolor all vertices of color $c_{1}$ with color $c_{2}.$

connect a $c_{1 }c_{2}:$ in graph containing vertex a create edges between all pairs of vertices where one vertex has color $c_{1}$ and the other has color $c_{2}.$ If $c_{1} = c_{2}$ loops are not created. If such an edge already exists, then the second parallel edge is created. Multi-edges are not allowed in this problem, so this case must not occur.

At the end we should have a single graph and colors of its vertices do not matter.

The minimal number of colors $ˆc$ , that can be used to construct a graph, is called a clique width of a graph. Clique width is one of the characteristics of graph complexity. Many NP-hard problems can be solved in polynomial time on graphs with bounded clique width, using dynamic programming on this process of building a graph. For a general graph, calculating the exact value of a clique width is known to be NP-hard. However, for some graph classes bounds on a clique width are known.

Cactus is a connected undirected graph in which every edge lies on at most one simple cycle. Intuitively cactus is a generalization of a tree where some cycles are allowed. Multi-edges (multiple edges between a pair of vertices) and loops (edges that connect a vertex to itself) are not allowed in a cactus. It is known that a clique width of a cactus does not exceed $4$ .

You are given a cactus. Find out how to build it in the described way using at most $ˆc = 4$ colors.

![](https://onlinejudgeimages.s3.amazonaws.com/problem/13991/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7%202016-12-22%20%EC%98%A4%ED%9B%84%207.31.10.png)

![](https://onlinejudgeimages.s3.amazonaws.com/problem/13991/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7%202016-12-22%20%EC%98%A4%ED%9B%84%207.31.21.png)

inputFormat:
The first line of the input file contains two integers $n$ and $m (1 \le n \le 50 000$ ; $0 \le m \le 50 000)$ . Here $n$ is the number of vertices in the graph. Vertices are numbered from $1$ to $n$ . Edges of the graph are represented by a set of edge-distinct paths, where $m$ is the number of such paths.

Each of the following $m$ lines contains a path in the graph. A path starts with an integer $k_{i} (2 \le k_{i } \le 1000)$ followed by $k_{i}$ integers from $1$ to $n$ . These $k_{i}$ integers represent vertices of a path. Adjacent vertices in the path are distinct. The path can go to the same vertex multiple times, but every edge is traversed exactly once in the whole input file.

The graph in the input file is a cactus.

outputFormat:
In the first line print one integer $q$ -- the number of operations you need. This number should not be greater than $10^{6}$ . In the next $q$ lines print operations. Each operation is denoted by its first letter (`j` for join, `r` for recolor and `c` for connect) and its arguments in the order they are described in the problem statement.

At the end, after applying all these operations, one should have one graph, which is equal to the cactus in the input. This means that there should be exactly one edge between each pair of vertices connected in the input graph, and no edges between vertices not connected in the input graph.

translation:
有 $n$ 个集合，初始第 $i$ 个集合只包含第 $i$ 个点，每个点的初始颜色都为 $1$。要求使用下列 $3$ 种操作构建出给定的仙人掌。输出方案，操作数不得多于 $10^6$。

- $j\ a\ b$，将 $a$ 所在的集合和 $b$ 所在的集合合并成一个集合。

- $r\ a\ c_1\ c_2$（$c_1,c_2\in[1,2,3,4]$），将 $a$ 所在的集合中，所有颜色为 $c_1$ 的点的颜色改为 $c_2$。

- $c\ a\ c_1\ c_2$，将 $a$ 所在的集合中，每一个颜色为 $c_1$ 的点连向每一个  颜色为 $c_2$ 的点，**不允许出现重边**。

输入第一行为点数 $n$ 和 $m$ 条（$n,m\leq 50000$）边不重复的路径，每条边**恰好**会出现一次。接下来每行第一个数字 $k_i$($2\leq k_i\leq1000$) 代表路径的点数，后面 $k_i$ 个数字表示一条路径。


title: [NEERC2016] Delight for a Cat

description:
A cat is going on an adventure.

Each hour, the cat can be either sleeping or eating. The cat cannot be doing both actions at the same hour, and the cat is doing exactly one of these actions for the whole hour.

For each of the next $n$ hours, the amount of delight the cat is getting if it is sleeping or eating during that hour is known. These amounts can be different for each hour.

An integer time period $k$ is also known. Among every $k$ consecutive hours, there should be at least $m_{s}$ hours when the cat is sleeping, and at least $m_{e}$ hours when the cat is eating. So, there are exactly $n − k + 1$ segments of $k$ hours for which this condition must be satisfied.

Find the maximum total amount of delight the cat can get during the next $n$ hours.

inputFormat:
The first line of the input contains four integers $n , k , m_{s},$ and $m_{e} (1 \le k \le n \le 1000$ ; $0 \le m_{s}, m_{e} \le k$ ; $m_{s} + m_{e} \le k)$ -- the number of upcoming hours, the length of the period (in hours), and the minimum number of hours the cat should be sleeping and eating out of every $k$ consecutive hours, respectively.

The second line contains $n$ integers $s_{1}, s_{2},$ . . . , $s_{n} (0 \le s_{i } \le 10^{9}$ ) -- the amount of delight the cat gets when it is sleeping during the first, the second, $ \cdots ,$ the n-th hour.

The third line contains $n$ integers $e_{1}, e_{2},$ . . . , $e_{n} (0 \le e_{i} \le 10^{9}$ ) -- the amount of delight the cat gets when it is eating during the first, the second, $ \cdots ,$ the n-th hour.

outputFormat:
In the first line, output a single integer -- the maximum total amount of delight the cat can get during the next $n$ hours.

In the second line, output a string of length $n$ consisting of characters `S` and `E`. The i-th character of this string should correspond to whether the cat should sleep $(`S`)$ or eat $(`E`)$ in the i-th hour to get the maximum total amount of delight out of these $n$ hours.

translation:
一只猫猫在连续的 $n$ 个小时中可以进行睡觉或进食两种动作。一个小时内只能选择其中一种进行。

现在你知道这只猫在接下来的这 $n$ 个小时中每第 $i$ 个小时睡觉或进食分别获得的快乐值 $s_i$ 和 $e_i$。

但是对于每一个连续的 $k$ 个小时，这只猫必须满足在这 $k$ 个小时内至少有 $m_e$ 个小时的进食时间和 $m_s$ 个小时的睡觉时间。也就是说在这 $n$ 个小时中的 $n-k+1$ 个 $k$ 长连续区间必须满足睡觉时间 $\geq m_s$ ，进食时间 $\geq m_e$。

现在小猫想知道自己这 $n$ 个小时最多能获得多少快乐值以及相对应的方案。

输入：

第一行分别输入 $n,k,m_s,m_e$ 。

第二行输入 $n$ 个数字 $s_1,s_2,\dots, s_n$ 分别代表每个小时如果睡觉可以获得的快乐值。

第三行输入 $n$ 个数字 $e_1,e_2,\dots,e_n$ 分别代表每个小时如果进食可以获得的快乐值。

输出：

第一行输出可以获得的最大快乐值。

第二行输出**一个合法方案**，$n$ 个字符表示每个小时进行的动作。第 $i$ 个字符用 `S` 表示第 $i$ 个小时在睡觉，或用 `E` 表示第 $i$ 个小时在进食。


title: [NEERC2016] Expect to Wait

description:
Mayor Adam East wants to improve the public transport network of Harshel city by introducing the network of stations with unicycles. Any person who owns a special card can come to a station and request a unicycle to ride or drop one.

The procedure of requesting a unicycle is simple. The person enters a queue. If there is a unicycle available, then the first person from the queue takes it immediately. Otherwise, people in the queue wait until someone drops a unicycle at the station.

Let the wait time be the time that person spends between the request (entrance to the queue) and obtaining a unicycle. If the person does not receive a unicycle at all, then the wait time is infinity. The total wait time is the sum of wait times for each person.

Adam already knows the schedule of all the people for every day. He knows at what times people request and drop unicycles at the Central Station that can hold any number of unicycles at the same time. The only thing he does not know is how many unicycles should be placed there at the start of each day. He asks you several questions to calculate the total wait time given the starting number of unicycles.

inputFormat:
The first line contains $n$ and $q (1 \le n , q \le 10^{5} ),$ where $n$ is the total number of unicycle requests and unicycle drops at the Central Station, and $q$ is the number of questions Adam asks you. The next $n$ lines describe operations at the Central Station. Each line contains one description of operation:

$`+ t$ k` when $k$ unicycles are dropped at time $t$ ;

$`- t$ k` when $k$ people request unicycles at time $t$ .

For each of the described operations $1 \le t \le 10^{9}$ and $1 \le k \le 10^{4}$ . The last line of the input contains $q$ different integers $b_{i} (0 \le b_{i} \le 10^{9}$ ) -- the number of unicycles at the start of the day.

The operations are given in the strongly increasing order of time.

outputFormat: The output shall consist of $q$ lines. The i-th line shall display the total wait time for the case of $b_{i}$ unicycles at the start of the day. If the total wait time is infinite, then the corresponding line shall display the word `INFINITY`.

translation:
# [NEERC2016] Expect to Wait

## 题目描述

市长小A想要给H市添加独轮车车站，任何有“特殊的卡片”的人，都可以到车站请求骑车或停放。

申请独轮车很简单，申请骑车的人到车站排队，如果那个站有独轮车停放，那么就让处于队头位置的人先骑，否则，排队的人会等到有人把独轮车送到车站。

定义等待时间为从请求人开始排队到取到车所花的时间，如果一个人取不到独轮车，那么等待的时间是无限（infinity）的。总等待时间是每个人等待时间的总和。

小A已经知道人们每天在什么时候向车站请求和放下独轮车，车站可以同时容纳无限独轮车。他会告诉你每天车站里人们的用车计划，然后对你进行n次询问，每次提问会告诉你一天开始时车站里有的独轮车数，请你来计算每个问题所对应的总等待时间。

## 输入格式

第一行包含两个正整数 $n$ 和 $q (1 \le n , q \le 10^{5} ),$ $n$代表有n个用车计划, $q$代表小A会问你n个问题 接下来$n$行代表每个用车计划，每个计划包含一个操作说明：

$+tk$ 代表人们在$t$时间要求停放$k$辆车;

$- t k$ 代表人们在$t$时间要求取$k$辆车.

对于每个用车计划： $1 \le t \le 10^{9}$ and $1 \le k \le 10^{4}$ . 输入的最后一行包含 $q$ 个不同的整数 $b_{i} (0 \le b_{i} \le 10^{9}$ ) -- 一天开始时独轮车的数量。

操作的顺序是按时间复杂度从小到大的

## 输出格式

输出应包括$q$行。第i行应显示当天开始时$b_{i}$独轮车的总等待时间。如果总等待时间是无限的，则相应的行应显示单词`INFINITY`。

## 样例 #1

### 样例输入 #1

```
5 4
- 1 1
- 2 2
+ 4 1
- 6 1
+ 7 2
0 3 1 2
```

### 样例输出 #1

```
INFINITY
0
8
3
```

## 提示

时间限制: 2 s,空间限制: 512 MB.


title: [NEERC2016] Foreign Postcards

description:
Fedor is an avid traveler. As a result of his hobby, he has gathered a big collection of postcards from all over the world. Each postcard has a unique picture on the front side and some fields for address information and text on the back side.

During one of the parties at Fedor's house, he decided to show all his of postcards to the guests. To achieve that, he wants to lay them all out on the table. Initially, all of his postcards are arranged in a single stack that Fedor is holding in his hands. Unfortunately, some of the postcards in that stack can be turned incorrectly -- upside down. Ideally, Fedor would like all postcards on the table to lie with the picture on top, but looking at every postcard and turning it over individually can be very time-consuming. Instead, he came up with the following process:

Let $n$ be the number of postcards remaining in the stack in his hands. Fedor chooses a random number $k$ uniformly between $1$ and $n$ and takes top $k$ postcards from the stack.

He looks at the topmost postcard among these $k$ postcards. If it is oriented in the wrong way, he turns the whole stack of $k$ postcards upside down together.

He then puts these $k$ postcards on the table without any further rotations.

If there are still some postcards remaining in the stack in his hands, Fedor goes back to step $1$ .

Of course, after all the postcards are on the table, there might still be some that lie back side up. What is the expected number of such postcards?

inputFormat: The input consists of a single line of `C` and `W` characters -- i-th character corresponds to i-th postcard in the stack, counting from the top of the stack. `C` means that i-th postcard is oriented correctly in the initial stack, and `W` means that i-th postcard is oriented in the wrong way. The number of characters is between $1$ and $10^{6}$ inclusive.

outputFormat: Output one real number -- the expected number of incorrectly placed postcards on the table. The absolute or relative error should not exceed $10^{−9}$ .

translation:
### 题目描述
费多是个热心的旅行者。由于他的爱好，他收集了来自世界各地的大量明信片。每张明信片正面都有一张独特的图片，背面有一些地址信息和文本字段。

在费多家的一次聚会上，他决定向客人展示他所有的明信片。为了实现这一目标，他想把它们全部摆在桌面上。起初，他所有的明信片都被安排在一个单叠里，费多拿在手里。不幸的是，这堆明信片中的一些可能会被错误地翻过来——颠倒过来。理想情况下，费多希望桌上的所有明信片都放在图片的上方，但查看每张明信片并逐个翻转可能非常耗时。相反，他提出了以下过程：

让 $n$ 是他手中的那堆明信片的剩余数量。费多均匀地选择一个介于1和 $n$ 之间的随机数 $k$ ，并从堆栈中取出前 $k$ 张明信片。

他看了看这 $k$ 张明信片中最上面的一张明信片。如果方向错误，他会将整叠明信片倒置在一起。

然后，他把这 $k$ 张明信片放在桌子上，不再旋转。

如果他手里还有一些明信片，费多会返回到步骤 $1$ 。

当然，在所有的明信片都放在桌子上之后，可能仍然有一些明信片是倒着放的。这类明信片的预期数量是多少？
### 输入格式
输入由一行 $C$ 和 $W$ 字符组成——第 $i$ 个字符对应于栈中的第 $i$ 个明信片，从栈顶部开始计数。$C$ 表示第 $i$ 张明信片在初始栈中的方向正确， $W$ 表示第 $i$ 张明信片的方向错误。字符数在 $1$ 到 $10^{6}$ 之间, $6$ 包括在内。
### 输出格式
输出一个实数——表上错误放置的明信片的预期数量。绝对或相对误差不应超过 $10^{−9}$
### 说明/提示
时间限制：2s，内存限制：512 MB。

hint:
Time limit: 2 s, Memory limit: 512 MB.

spj 由 [tiger2005](https://www.luogu.com.cn/user/60864) 提供。


title: [NEERC2016] Game on Graph

description:
Gennady and Georgiy are playing interesting game on a directed graph. The graph has $n$ vertices and $m$ arcs, loops are allowed. Gennady and Georgiy have a token placed in one of the graph vertices. Players take turns moving the token along one of the arcs that starts in the vertex the token is currently in. When there is no such arc, then this player loses the game.

For each initial position of the token and the player who is moving first, your task is to determine what kind of result the game is going to have. Does it seem to be easy? Not so much.

On one side, Gennady is having a lot of fun playing this game, so he wants to play as long as possible. He even prefers a strategy that leads to infinite game to a strategy that makes him a winner. But if he cannot make the game infinite, then he obviously prefers winning to losing.

On the other side, Georgiy has a lot of other work, so he does not want to play the game infinitely. Georgiy wants to win the game, but if he cannot win, then he prefers losing game to making it infinite.

Both players are playing optimally. Both players know preferences of the other player.

inputFormat: In the first line there are two integers -- the number of vertices $n (1 \le n \le 100 000)$ and the number of arcs $m (1 \le m \le 200 000)$ . In the next $m$ lines there are two integers a and $b$ on each line, denoting an arc from vertex a to vertex $b$ . Vertices are numbered from $1$ to $n$ . Each $(a , b)$ tuple appears at most once.

outputFormat: In the first line print $n$ characters -- i-th character should denote the result of the game if Gennady starts in vertex $i$ . In the second line print $n$ characters -- i-th character should denote the result of the game if Georgiy starts in vertex $i$ . The result of the game is denoted by `W` if the starting player wins the game, `L` if the starting player loses the game, and `D` (draw) if the game runs infinitely.

translation:
Gennady 和 Georgiy 在玩一个有向图上的游戏。这个图有 $n$ 个点 $m$ 条边，两人轮流操作，每次可以将棋子沿着其中一条边移动，不能移动者输。

你要对于每个点，分别求出以这个店为起点开始游戏，两人分别作为先手，最终会输，赢，还是平局（游戏无限循环）。

其中，Gennady 因为玩得很开心，所以他更期望将游戏变为平局；Georgiy 还有很多其他事，所以他更期望游戏不要平局。当然，在不平局的基础上，两人都更希望赢。

### 输入格式

第一行两个数 $n$，$m$ 表示有 $n$ 个点 $m$ 条边。
接下来 $m$ 行每行两个数 $a,b$ 表示一条由 $a$ 至 $b$ 的边。

### 输出格式
两行，第一行表示分别以每一个点为起点 Gennady 先手的胜负情况；第二行表示分别以每一个点为起点 Georgiy 先手的胜负情况。`W` 表示赢，`L` 表示输，`D` 表示平局。

by a___


title: [ICPC2021 WF] Where Am I?

description:
Who am I? What am I? Why am I? These are all difficult questions that have kept philosophers reliably busy over the past millennia. But when it comes to "Where am I", then, well, modern smartphones and GPS satellites have pretty much taken the excitement out of that question.

To add insult to the injury of newly unemployed spatial philosophers formerly pondering the "where" question, the Instant Cartographic Positioning Company (ICPC) has decided to run a demonstration of just how much more powerful a GPS is compared to old-fashioned maps. Their argument is that maps are useful only if you already know where you are, but much less so if you start at an unknown location.

For this demonstration, the ICPC has created a test area that is arranged as an unbounded Cartesian grid. Most grid cells are empty, but a finite number of cells have a marker at their center (see Figure L.1(a) for an example with five marked cells). All empty grid cells look the same, and all cells with markers look the same. Suppose you are given a map of the test area (that is, the positions of all the markers), and you are placed at an (unknown to you) grid cell. How long will it take you to find out where you actually are? ICPC's answer is clear: potentially a very, very long time, while a GPS would give you the answer instantly. But how long exactly?

![](https://cdn.luogu.com.cn/upload/image_hosting/ydxjurja.png)

Figure L.1: Sample grid and the order in which test subjects explore the grid.

In the trial, test subjects will explore their environment by following an expanding clockwise spiral whose first few steps are shown in Figure L.1(b). The starting cell is labeled "0", and the numbers show the order in which other cells are visited. The test subjects can see a marker only if they are at its grid cell, and they will stop their exploration as soon as they know where they are based on the grid cells that they have seen so far. That means that the observed sequence of empty and marked grid cells could have begun only at a single possible starting position. The grid is unbounded, but the exploration will be finite since once a test subject has seen all markers on the grid, they'll definitely know where they are.

Having hundreds of test subjects literally running in circles can be expensive, so the ICPC figures that writing a simulation will be cheaper and faster. Maybe you can help?

inputFormat:
The input describes a single grid. It starts with a line containing two integers $d_x$ , $d_y$ ($1 \leq d_x, d_y \leq 100$). The following $d_y$ lines contain $d_x$ characters each, and describe part of the test grid. The $i^{th}$ character of the $j^{th}$ line of this grid description specifies the contents of the grid cell at coordinate ($i$, $d_y-j+1$). The character is either '$\texttt{.}$' or '$\texttt{X}$', meaning that the cell is either empty, or contains a marker, respectively.

The total number of markers in the grid will be between $1$ and $100$, inclusive. All grid cells outside the range described by the input are empty.

outputFormat:
In ICPC's experiment, a test subject knows they will start at some position ($x$, $y$) with $1 \leq x \leq d_x$, $1 \leq y \leq d_y$.

Output three lines. The first line should have the expected number of steps needed to identify the starting position, assuming that the starting position is chosen uniformly at random. This number needs to be exact to within an absolute error of $10^{-3}$.

The second line should have the maximum number of steps necessary until one can identify the starting position.

The third line should list all starting coordinates ($x$, $y$) that require that maximum number of steps. The coordinates should be sorted by increasing $y$-coordinates, and then (if the $y$-coordinates are the same) by increasing $x$-coordinates.

translation:
输入描述:

一个单独的网格。它以包含两个整数 dx, dy (1≤dx, dy≤100) 的一行开始。接下来的 dy 行每行包含 dx 个字符，并描述了测试网格的一部分。网格描述的第 i 行第 j 列的字符指定了坐标 (i, dy-j+1) 处网格单元的内容。字符可以为 '.' 或 'X'，分别表示该单元格为空或包含标记。

网格中标记的总数将在1到100之间，包括1和100。输入未包含的网格单元都为空。

输出三行。

第一行应该是估计需要识别起始位置的步骤数，假设起始位置是均匀随机选择的。这个数需要精确到$10^{-3}$的绝对误差。

第二行应该是识别起始位置所需的最大步骤数。

第三行应该列出所有需要最大步骤数的起始坐标(x, y)。坐标应按递增的y坐标排序，如果y坐标相同，则按递增的x坐标排序。


title: [NEERC2016] Jenga Boom

description:
Jane is a game designer and she designs the next version of Jenga Boom, where the blocks have dimensions of $1 \times w \times w_n$ instead of the ordinary $1 \times 2 \times 6$ . As usual, the initial tower is created at the game start. It consists of the blocks in levels of $n$ blocks placed next to each other along their long sides and at a right angle to the previous level. Players remove blocks from the tower in turns, until the tower collapses.

![](https://onlinejudgeimages.s3.amazonaws.com/problem/13998/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7%202016-12-22%20%EC%98%A4%ED%9B%84%208.10.49.png)

Initial tower

![](https://onlinejudgeimages.s3.amazonaws.com/problem/13998/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7%202016-12-22%20%EC%98%A4%ED%9B%84%208.11.00.png)

The tower before collapse

Jane wants to build a game simulator that helps her to decide the best $n$ and $w$ . The simulator shall compute the moment when the tower collapses if blocks are removed in the specified order. Tower collapses if there is a cross-section between levels such that the center of the mass of the levels above it does not belong to or is at the edge of the convex hull of the previous level projection.

inputFormat:
The first line contains two integers $n$ and $w$ that define the dimensions of the block as described in the problem statement $(1 \le n , w \le 10 000)$ . The second line also contains two integers: $h$ -- the number of levels in the tower and $m$ -- the number of removed blocks $(1 \le h , m \le 5 000)$ .

The next $m$ lines contain coordinates of the removed blocks with two integers each: $l_{i}$ -- the level of the block, counting from the bottom and $k_{i}$ -- the position of the block, counting from the edge nearest to the players $(1 \le l_{i} \le h$ ; $1 \le k_{i} \le n)$ . Blocks are removed one by one and no block is removed twice.

outputFormat: In the first line output `yes` if the tower collapses, and `no` otherwise. In the former case, output the number of the block (starting from $1$) , that was removed just before the collapse, in the next line.

translation:
设有一个塔，它的积木块是 $1\times w\times (w\times n)$ 的长方体，每层由 $n$ 个积木块，每两层交错摆放，共有 $h$ 层。有 $m$ 个抽积木的操作，对于第 $i$ 个操作给出从底往上数的第 $l_i$ 层和从左后方往右前方数的第 $k_i$ 块。某一层的左边或右边加上中间 (如果 $n$ 为偶数，那么忽略中间) 的积木块全被抽完，则塔倒塌。

#### 输入格式
第一行为 $n$ 和 $w$ ，($1\le n,w\le10000$) 。第二行为 $h$ 和 $m$  ,($1\le h,m\le5000$)。接下来的 $m$ 行为 $l_i$ 和 $k_i$ ($1\le l_i\le h;1\le k_i\le n$) 。一块积木只能移动一次。
#### 输出格式
如果塔能倒塌，则输出 "yes" 。否则输出 "no" 。对于第一种情况，在下一行输出倒塌前一步的编号 $i$ 。


title: [NEERC2016] Kids Designing Kids

description:
Kevin and Kimberly have freckles on their foreheads.

They both drew their freckle pictures on sheets of paper. Each picture is a rectangle of `pixels`: every cell either has a freckle or it has no freckle.

They are jokingly proposing that when they grow up, marry, and have a child, her freckle picture is produced as a result of the following procedure:

Kevin's and Kimberly's pictures are moved by a parallel translation, and then in each cell a child has a freckle if and only if exactly one of the parents has a freckle in this position.

Now they wonder, whether there is a parallel translation that gives their child a specific freckle picture (for example, a lightning), and what is this parallel translation.

inputFormat:
The first line contains two integers, $h_{1 }and w_{1} (1 \le h_{1}, w_{1} \le 1000)$ -- the height and the width of Kevin's freckle picture. Each of the next $h_{1}$ lines consists of $w_{1}$ characters $‘ \times '$ and $‘. '.$ Character $‘ \times '$ means that there is a freckle, and $‘. '$ that there is not.

The next lines contain Kimberly's picture in the same format. Its height and width $h_2$ and $w_2$ follow the same constraints.

It is guaranteed that Kevin and Kimberly have at least one freckle each.

The next lines contain the picture they want for their child in the same format. Its dimensions $h_{3}$ and $w_{3}$ also have the same constraints.

outputFormat:
In the first line output `YES` if the desired picture can be produced, and `NO` otherwise.

If the answer is positive, then in the second line output two integers, $x$ and $y$ , with the following meaning: if you overlay the pictures so that their upper left corners coincide, then move Kimberly's picture $x$ cells right (negative number means moving picture left) and $y$ cells down (negative number means moving picture up), and then apply the procedure described above, the resulting picture can be moved by a parallel translation to coincide with the third picture from the input file.

translation:
给定三个 01 矩阵（``*`` 表示 $1$，``.`` 表示 $0$），大小分别为 $h_1\times w_1$、$h_2\times w_2$ 和 $h_3\times w_3$，你可以将前两个矩阵的左上角重叠，然后将第二个矩阵向右平移 $x$ 个长度、向下平移 $y$ 个长度（$x,y$ 可以为负数，表示反方向）。然后将对应位置异或起来（超出部分均视为 $0$）。

你需要判断得到的矩阵是否可能能够通过平移和第三个矩阵重合（超出部分均视为 $0$），并给出方案。

保证前两个矩阵都含有至少一个 $1$。

$h,w\le 10^3$。


title: [NEERC2016] List of Primes

description:
Lidia likes sets of prime numbers. When she is bored, she starts writing them down into the Extremely Long Notebook for Prime Sets.

Elements of each set are written down in ascending order. Each set of prime numbers appears in her notebook eventually. A set with a smaller sum always appears before a set with a larger sum. Sets with the same sum are sorted in ascending lexicographical order: they are compared by the first element, if the first elements are equal, then by second element, and so on.

Just in case someone decides to parse her notebook, she writes down her sets in a machine-readable JSON format. Of course, she puts a space after each comma. Here's the beginning of her notebook:

$[2], [3], [2 , 3], [5], [2 , 5], [7], [3 , 5], [2 , 7], [2 , 3 , 5], [3 , 7], [11], [2 , 3 , 7], [5 , 7], [2 , 11], [13], [2 , 5 , 7],$

Lidia wants to double-check her work, so here is her request for you: given two integers, $a$ and $b$ , output a substring of her notebook from the position $a$ to the position $b$ (inclusive, counting from $1$) .

inputFormat: The first line contains two integers, $a$ and $b$ ($1 \le a \le b \le 10^{18}; b - a \le 10^{5}$).

outputFormat: Output the substring of the notebook described in the problem statement from the position $a$ to the position $b$ . You must write a line with exactly $b - a + 1$ characters, including any leading or trailing spaces.

translation:
Lidia 喜欢素数集。当她无聊时，她就把它们写进她的「素数集的超长笔记本」。

集合中的元素按升序排列。每个集合都会在她的笔记本里出现，且以元素和为第一关键字，字典序为第二关键字排列。

为了预防有人决定解析她的笔记本，她把她的集合写成了机器可读的 JSON 格式。当然，她在每个逗号后面都加了空格。以下是她的笔记本的开头：

$$
[2], [3], [2 , 3], [5], [2 , 5], [7], [3 , 5], [2 , 7], [2 , 3 , 5], [3 , 7], [11], [2 , 3 , 7], [5 , 7], [2 , 11], [13], [2 , 5 , 7],
$$

Lidia 想仔细检查她的工作，所以她给了你两个整数 $a$ 和 $b$，要你输出她的笔记本中第 $a$ 到 $b$ 个字符（含两端，从 $1$ 开始）的内容。


title: [NEERC2015] Adjustment Office

description:
가리송과 안드레송은 정산소에서 일하고 있고, 미래를 예측하고자 한다. 둘에게는 큰 $n,x,n$ 정사각형이 주어진다。처음에 각 배열의 원소 $(x,y)$ 는 $x + y$ 로 채워져있다. $(1 \le x , y \le n)$.

미래 예측을 하는데에 두가지 타입의 쿼리가 들어온다.

- `R r` —$r$ 행의 모든 값들을 합한 결과를 출력하고, $r$ 행을 모두 $0$ 으로 바꾼다.
- `C c`—$c$ 열의 모든 값들을 합한 결과를 출력하고, $c$ 열을 모두 $0$ 으로 바꾼다.

쿼리 결과를 구하는 프로그램을 작성하시오.

inputFormat:
첫줄에는 배열의 크기 $n$ 과 쿼리의 개수 $q$ 가 입력된다. $(1 \le n \le 10^{6}, 1 \le q \le 10^{5})$.

그 다음 $q$ 개의 줄마다 `R r` (1 \le r \le n) 혹은 `C c` (1 \le c \le n)인 쿼리문이 입력된다.

outputFormat: $q$ 개의 줄에 걸쳐서 $i$ 번째 쿼리의 결과를 출력한다. $(1 \le i \le q)$.

translation:
有一个大小为 $n\times n$ 的矩阵，每个位置的值为该位置的行数+列数。

接下来有 $q$ 次操作：

- $R\ m$：输出第 $m$ 行的总和并整行消去。
- $C\ m$：输出第 $m$ 列的总和并整列消去。

$1\leqslant n\leqslant 10^6$，$1\leqslant q\leqslant 10^5$，$1\leqslant m\leqslant n$。

Translated by Eason_AC
2020.11.19

hint: Time limit: 1 s, Memory limit: 256 MB.


title: [NEERC2015] Cactus Jubilee

description:
This is the $20-th$ Northeastern European Regional Contest $(NEERC).$ Cactus problems had become a NEERC tradition. The first Cactus problem was given in $2005$ , so there is a jubilee -- $10$ years of Cactus.

Cactus is a connected undirected graph in which every edge lies on at most one simple cycle. Intuitively cactus is a generalization of a tree where some cycles are allowed. Multiedges (multiple edges between a pair of vertices) and loops (edges that connect a vertex to itself) are not allowed in a cactus.

You are given a cactus. Let's move an edge -- remove one of graph's edges, but connect a different pair of vertices with an edge, so that a graph still remains a cactus. How many ways are there to perform such a move?

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/11737/1.png)

For example, in the left cactus above (given in the first sample), there are $42$ ways to perform an edge move. In the right cactus (given in the second sample), which is the classical NEERC cactus since the original problem in $2005$ , there are $216$ ways to perform a move.

inputFormat:
The first line of the input file contains two integers $n$ and $m (1 \le n \le 50 000 , 0 \le m \le 50 000)$ . Here $n$ is the number of vertices in the graph. Vertices are numbered from $1$ to $n$ . Edges of the graph are represented by a set of edge-distinct paths, where $m$ is the number of such paths.

Each of the following $m$ lines contains a path in the graph. A path starts with an integer $k_{i} (2 \le k_{i} \le 1000)$ followed by $k_{i}$ integers from $1$ to $n$ . These $k_{i}$ integers represent vertices of a path. Adjacent vertices in a path are distinct. Path can go to the same vertex multiple times, but every edge is traversed exactly once in the whole input file.

The graph in the input file is a cactus.

outputFormat: Write to the output file a single integer -- the number of ways to move an edge in the cactus.

translation:
题目描述

定义一种无向连通图叫`仙人掌图（Cactus图）`。仙人掌图中没有重边和自环，并且其中的每一条边至多位于一个简单环上。简单地说，`仙人掌图`是树的一种泛化形式，其中允许出现一些环。

现在有一个`仙人掌图`，你每次可以移动一条边（移除图的一条边，并将另一对顶点用一条边连接起来）。问如果要让后来得到的新图仍然是`仙人掌图`，有多少种移动边的办法？

输入格式

第一行包含两个整数n和m，分别表示图中的顶点数（顶点的编号分别为${1,2,3,...,n}$）和边的数目，且满足
$$1≤n≤50000,0≤m≤50000$$

第2~m+1行，每一行表示一条路径（从一个顶点出发一直往后走，直到当前所在的顶点没有任何未走过一条边）。

（译者注：虽然应该都能看出来了，但是还是用一个递归函数更浅显易懂）

设路径的开始点为$q_1$，$E_i$表示第$i$个点的边,$vis$数组中存储已经走过了的边，则整条路径可定义为：
```
1.x←q1
2.f(x)
	1.add(vis[],x)
	2.for i∈Ex do
	1.if i not in vis[] then
		1.call f(i->to)
3.print(vis[])
```
即：每一行的开始有一个整数$k_i$，满足
$2≤k_i≤1000$，紧接着有$k_i$个整数，表示这条路径所经过的顶点$q_i$，满足$q_i∈[1,n]$。

数据保证路径中的相邻顶点是不同的。

在路径中可以多次到达同一个顶点，但在整个输入文件中，每条边只遍历一次。

数据保证输入文件中的图形是仙人掌。

输出格式

输出文件中只有一个整数，即移动`仙人掌图`中一条边的方法数。

数据范围
$$1≤n≤50000,0≤m≤50000,2≤k_i≤1000,q_i∈[1,n]$$


title: [NEERC2015] Distance on Triangulation

description:
You have a convex polygon. The vertices of the polygon are successively numbered from $1$ to $n$ . You also have a triangulation of this polygon, given as a list of $n − 3$ diagonals.

You are also given $q$ queries. Each query consists of two vertex indices. For each query, find the shortest distance between these two vertices, provided that you can move by the sides and by the given diagonals of the polygon, and the distance is measured as the total number of sides and diagonals you have traversed.

inputFormat:
The first line of the input file contains an integer $n$ -- the number of vertices of the polygon $(4 \le n \le 50 000)$ .

Each of the following $n−3$ lines contains two integers $a_{i}, b_{i}$ -- the ends of the i-th diagonal $(1 \le a_{i}, b_{i} \le n , a_{i} ≠ b_{i}).$

The next line contains an integer $q$ -- the number of queries $(1 \le q \le 100 000)$ .

Each of the following $q$ lines contains two integers $x_{i}, y_{i}$ -- the vertices in the i-th query $(1 \le x_{i}, y_{i} \le n)$ .

It is guaranteed that no diagonal coincides with a side of the polygon, and that no two diagonals coincide or intersect.

outputFormat: For each query output a line containing the shortest distance.

translation:
给定一个正 $n$ 边形及其三角剖分, 共 $2n−3$ 条边 ($n$ 条多边形的边和 $n−3$ 条对角线), 每条边的长度为 $1$。

共 $q$ 次询问, 每次询问给定两个点, 求它们的最短距离。

Translated by Eason_AC
2020.11.19

hint: Time limit: 2 s, Memory limit: 256 MB.


title: [NEERC2015] Easy Problemset

description:
Perhaps one of the hardest problems of any ACM ICPC contest is to create a problemset with a reasonable number of easy problems. On Not Easy European Regional Contest this problem is solved as follows.

There are $n$ jury members (judges). They are numbered from $1$ to $n$ . Judge number $i$ had prepared $p_{i}$ easy problems before the jury meeting. Each of these problems has a hardness between $0$ and $49$ (the higher the harder). Each judge also knows a very large (say infinite) number of hard problems (their hardness is $50$) . Judges need to select $k$ problems to be used on the contest during this meeting.

They start to propose problems in the ascending order of judges numbers. The first judge takes the first problem from his list of remaining easy problems (or a hard problem, if he has already proposed all his easy problems) and proposes it. The proposed problem is selected for the contest if its hardness is greater than or equal to the total hardness of the problems selected so far, otherwise it is considered too easy. Then the second judge does the same etc. ; after the n-th judge, the first one proposes his next problem, and so on. This procedure is stopped immediately when $k$ problems are selected.

If all judges have proposed all their easy problems, but they still have selected less than $k$ problems, then they take some hard problems to complete the problemset regardless of the total hardness.

Your task is to calculate the total hardness of the problemset created by the judges.

inputFormat: The first line of the input file contains the number of judges $n (2 \le n \le 10)$ and the number of problems $k (8 \le k \le 14)$ . The i-th of the following $n$ lines contains the description of the problems prepared by the i-th judge. It starts with $p_{i} (1 \le p_{i} \le 10)$ followed by $p_{i}$ non negative integers between $0$ and $49$ -- the hardnesses of the problems prepared by the i-th judge in the order they will be proposed.

outputFormat: Output the only integer -- the total hardness of the selected problems.

translation: 有 $n$ 位出题人，他们要出 $k$ 道题。他们有一定数量的难度在 $0$ 到 $45$ 之间的简单题，和无限多道难度为 $50$ 的难题。出题人依次出题，每一位出题人都会选择他剩余的简单题目中的第一道，如果这道题目的难度大于等于之前选择的所有题目的难度之和，则会采用这道题目，否则就会丢弃这道题目。如果一位出题人的所有简单题目都用完了，他就会使用难题。直到选够了 $k$ 道题目，他们才会停止选题。


title: [NEERC2015] Froggy Ford（征集SPJ）

description:
Fiona designs a new computer game Froggy Ford. In this game, a player helps a frog to cross a river using stone fords. Frog leaps from the river's shore to the first stone ford, than to the second one and so on, until it reaches the other shore. Unfortunately, frog is pretty weak and its leap distance is quite limited. Thus, a player should choose the optimal route -- the route that minimizes the largest leap required to traverse the route.

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/11740/1.png)

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/11740/2.png)

Optimal route

Optimal route with added stone

Fiona thinks that this game is not challenging enough, so she plans to add a possibility to place a new stone in the river. She asks you to write a program that determines such a location of the new stone that minimizes the largest leap required to traverse the optimal route.

inputFormat:
The first line of the input file contains two integers $w$ -- the width of the river and $n$ -- the number of stones in it $(1 \le w \le 10^{9}, 0 \le n \le 1000)$ .

Each of the following $n$ lines contains two integers $x_{i}, y_{i}$ -- the coordinates of the stones $(0 < x_{i} < w , −10^{9} \le y_i \le 10^{9}).$ Coordinates of all stones are distinct. River shores have coordinates $x = 0$ and $x = w$ .

outputFormat: Write to the output file two real numbers $x_{+}$ and $y_{+} (0 < x_{+} < w , −10^{9} \le y_{+} \le 10^{9})$ -- the coordinates of the stone to add. This stone shall minimize the largest leap required to traverse the optimal route. If a new stone cannot provide any improvement to the optimal route, then an arbitrary pair of $x_{+}$ and $y_{+}$ satisfying the constraints can be written, even coinciding with one of the existing stones. Your answer shall be precise up to three digits after the decimal point.

translation:
## **题目描述**
Fiona设计了一款新的电脑游戏《青蛙渡河》。在这个游戏中，玩家用石头当浅滩帮助青蛙过河。青蛙从河岸跳到第一个石滩，然后跳到第二个石滩等等，直到到达另一个岸。不幸的是，青蛙非常虚弱，它的跳跃距离非常有限。因此，玩家应该选择最佳路线——使穿越路线所需的最大跳跃最小化的路线。Fiona认为这个游戏不够有挑战性，所以她计划增加一种可能性，在河里放一块新石头。她要求你编写一个程序，确定新石头的位置，以最小化穿越最佳路线所需的最大跳跃。
## **输入格式**
输入文件的第一行包含两个整数w n,表示河流的宽度和其中的石头数量（1<=w<=10^9，0<=n<=1000）
接下来的n行，每行包含两个整数，x[i]和y[i],表示每块石头的坐标（0<x[i]<w,-10^9<=y[i]<=10^9）。所有石头的坐标是不同的，河岸为x=0和x=w的两条直线。
## **输出格式**
向输出文件写入两个实数x+和y+,表示要添加的石头的坐（0<x<w,-10^9<=y<=10^9）, 这块石头应尽量减少穿越最佳路线所需的最大跳跃，如果一个新的石头不能对最优路径提供任何改进，那么可以编写任意一对满足约束条件的石头，甚至可以与现有的一块石头重合。你的输出应精确到小数点后三位。
#### （样例数据见原题面）
## **说明与提示**
时间限制：1s  内存限制：256MB


title: [NEERC2015] Generators

description:
Little Roman is studying linear congruential generators -- one of the oldest and best known pseudorandom number generator algorithms. Linear congruential generator (LCG) starts with a non-negative integer number $x_{0}$ also known as seed and produces an infinite sequence of non-negative integer numbers $x_{i} (0 \le x_{i} < c)$ which are given by the following recurrence relation:

$x_{i+1} = (ax_{i} + b)$ mod $c$

here a , $b$ , and $c$ are non-negative integer numbers and $0 \le x_{0} < c$ .

Roman is curious about relations between sequences generated by different LCGs. In particular, he has $n$ different LCGs with parameters $a^{(j)}, b^{(j)},$ and $c^{(j)}$ for $1 \le j \le n$ , where the j-th LCG is generating a sequence $x_{i}^{(j)}.$ He wants to pick one number from each of the sequences generated by each LCG so that the sum of the numbers is the maximum one, but is not divisible by the given integer number $k$ .

Formally, Roman wants to find integer numbers $t_{j} \ge 0$ for $1 \le j \le n$ to maximize $s = Σ^{n}_{j=1} x_{t_{j}}^{(j)}  subject$ to constraint that $s$ mod $k ≠ 0$ .

inputFormat: The first line of the input file contains two integer numbers $n$ and $k (1 \le n \le 10 000 , 1 \le k \le 10^{9}).$ The following $n$ lines describe LCGs. Each line contains four integer numbers $x_{0}^{(j)}, a^{(j)}, b^{(j)},$ and $c^{(j)} (0 \le a^{(j)}, b^{(j)} \le 1000 , 0 \le x_{0}^{(j)} < c^{(j)} \le 1000)$ .

outputFormat:
If Roman's problem has a solution, then write on the first line of the output file a single integer $s$ -- the maximum sum not divisible by $k$ , followed on the next line by $n$ integer numbers $t_{j} (0 \le t_{j} \le 10^{9})$ specifying some solution with this sum.

Otherwise, write to the output file a single line with the number $−1$ .

translation:
### 题目描述

罗曼在学习线性同余发生器——最古老，也是最广为人知的伪随机数生成算法之一。线性同余发生器（LCG）以 $x_0$ 为随机种子，生成很多非负整数 $x_i$ ,它遵循以下规则：

给定非负整数 $a,b,c\space(0≤x_0<c)$ ，
$x_{i+1} = (ax_i+b)\space mod \space c$

罗曼很好奇由不同LCG产生的序列之间的关系。特别地，他有 $n$ 个不同的LCG，含有参数 $a^{(j)}, b^{(j)}, c^{(j)}\space(1≤j≤n)$。第 $j$ 个LCG会生成一个序列 $x_i^{(j)}$ 。

他希望能从每个LCG产生的序列中挑出一个数，使他们的和最大，且不被给定的 $k$ 整除。

**格式化一点来说**，他希望找到整数 $t_j \space(t_j>0,1≤j≤n)$ ，使$s=\sum\limits_{j=1}^nx_{t_j}^{(j)}$最大，且$s\not\equiv0(mod\space k)$。

### 输入格式

第 $1$ 行包括两个整数$n,k$。

$(1≤n≤10000,1≤k≤10^9)$

接下来 $n$ 行描述LCG，每行包括4个整数：$x_0^{(j)},a^{(j)}, b^{(j)}, c^{(j)}$ 。

$(0≤a^{(j)}, b^{(j)}≤1000,0≤x_0^{(j)}<c^{(j)}≤1000)$

### 输出格式

如果有解，第 $1$ 行输出 $s$，第 $2$ 行输出 $n$ 个 $t_j$ 。

$(0≤t_j≤10^9)$ 。

如果无解，输出 $-1$ 。

### 说明/提示
时间限制：1秒

空间限制：256MB


title: [NEERC2015] Hypercube

description:
Consider a $4-hypercube$ also known as tesseract. A unit solid tesseract is a 4D figure that is equal to the convex hull of $16$ points with Cartesian coordinates $(±½, ±½, ±½, ±½)$ -- its vertices. It has $32$ edges $(1D), 24$ square faces $(2D),$ and $8$ cubic $3-faces$ (3D) also known as cells. We study hollow tesseracts and define a tesseract as a boundary of a solid tesseract. Thus, a tesseract is a connected union of $8$ solid cubes (its cells) that intersect between each other at $24$ tesseract's square faces, $32$ edges, and $16$ vertices.

Let's cut a tesseract along $17$ of its $24$ faces, so that it still remains connected via $7$ faces that were left intact. Unfold the tesseract into a 3D hyperplane by rotating its constituting cubes along the faces that were left intact until all its cells lie in the same 3D hyperplane. The result is called a $3-net$ of a tesseract. This process is a natural generalization of how a 3D cube is cut and unfolded onto a 2D plane to produce a $2-net$ of a cube that consists of $6$ squares.

In this problem you are given a tree-like $8-polycube$ in 3D space also known as octocube. An octocube is a collection of $8$ unit cubical cells joined face-to-face. More formally, intersection of each pair of cubical cells constituting an octocube is either empty, a point, a unit line $(1D),$ or a unit square $(2D).$ The given octocube is tree-like in the following sense. Consider an adjacency graph of the octocube -- a graph with $8$ vertices corresponding to its $8$ cells. There is an edge in the adjacency graph between pairs of adjacent cells. Two cells of an octocube are called adjacent when their intersection is a square. Cells that intersect at a point or a line are not considered adjacent. An octocube is called tree-like when its adjacency graph is a tree.

Your task is to determine whether the given tree-like octocube constitutes a $3-net$ of a tesseract. That is, whether this octocube being put onto a hyperplane in 4D space can be folded in 4D space along the squares of intersection between its cells into a tesseract.

For example, look at the leftmost picture below. It shows a wire-frame of the tree-like octocube. Rotate cell $GHLKG_{1}H_{1}L_{1}K_{1}$ around a plane GHLK and cell $FGKJF_{2}G_{2}K_{2}J_{2}$ around a plane FGKJ at angle $90$ degrees in $4-th$ dimension outside of the original hyperplane. As a result, point $G_{1}$ joins with $G_{2}$ and $K_{1}$ joins with $K_{2}.$ The face $GKK_{2}G_{2}$ is glued to face $GKK_{1}G_{1}.$ The result is shown on the right. The $4-th$ dimension is orthographically projected onto the $3$ shown in perspective. The points that have moved out of the original hyperplane are marked with hollow dots.

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/11742/1.png)

Rotate $EFJIE_{1}F_{1}J_{1}I_{1}$ around EFJI and $EHLIE_{2}H_{2}L_{2}I_{2}$ around EHLI. The result is shown on the following picture on the left. The remaining steps are as follows. Rotate MNOPQRST around MNOP, then rotate both MNOPQRST and IJKLMNOP around IJKL and rotate ABCDEFGH around EFGH. The last step is to glue all faces that meet together to get a tesseract that is shown on the right.

![](https://onlinejudgeimages.s3-ap-northeast-1.amazonaws.com/problem/11742/2.png)

inputFormat: The first line of the input file contains there integers $m , n , k$ -- the width, the depth, and the height of the box that contains the given octocube $(1 \le m , n , k \le 8)$ . The following $k$ groups of lines describe rectangular slices of the box from top to bottom. Each slice is described by $n$ rows with $m$ characters each. The characters on a line are either $‘. ',$ denoting an empty space, or $‘x',$ denoting a unit cube. The input file is guaranteed to describe a tree-like octocube.

outputFormat: Write to the output file a single word `Yes` if the given octocube can be folded into a tesseract or `No` otherwise.

translation: 给定一个三维图形，保证相邻小方格之间构成树形结构，判断它是否是4维超立方体的一个三维展开。