title: [CERC2013] Captain Obvious and the Rabbit-Man

description:
It's you, Captain Obvious! - cried the evil Rabbit-Man - you came here to foil my evil plans!

Yes, it's me.  - said Captain Obvious.

But... how did you know that $I$ would be here, on $625$ Sunflower Street?! Did you crack my evil code?

I did. Three days ago, you robbed a bank on $5$ Sunflower Street, the next day you blew up $25$ Sunflower Street, and yesterday you left quite a mess under number $125$ . These are all powers of $5$ . And last year you pulled a similar stunt with powers of $13$ . You seem to have a knack for Fibonacci numbers, Rabbit-Man.

That's not over! $I$ will learn... arithmetics! - Rabbit-Man screamed as he was dragged into custody - You will never know what to expect... Owww! Not my ears, you morons!

Maybe, but right now you are being arrested.  - Captain added proudly.

Unfortunately, Rabbit-Man has now indeed learned some more advanced arithmetics. To understand it, let us define the sequence $F_n$ (being not completely unlike the Fibonacci sequence):

$F_{1} = 1$ ,

$F_{2} = 2$ ,

$F_{n} = F_{n-1} + F_{n-2}$ for $n \ge 3$ .

Rabbit-Man has combined all his previous evil ideas into one master plan. On the i-th day, he does a malicious act on the spot number $p(i)$ , defined as follows:

$p(i) = a_{1}·F_{1}^{i} + a_{2}·F_{2}^{i} + \cdots + a_{k}·F_{k}^{i}.$

The number $k$ and the integer coefficients $a_1 , \cdots $ , ak are fixed. Captain Obvious learned $k$ , but does not know the coefficients. Given $p(1) , p(2) , \cdots , p(k)$ , help him to determine p(k $+ 1)$ . To avoid overwhelmingly large numbers, do all the calculations modulo a fixed prime number $M$ . You may assume that $F_1 , F_2 , \cdots , F_n$ are pairwise distinct modulo $M$ . You may also assume that there always exists a unique solution for the given input.

inputFormat:
The first line of input contains the number of test cases $T$ . The descriptions of the test cases follow:

The first line of each test case contains two integers $k$ and $M , 1 \le k \le 4000 , 3 \le M \le 10^{9}.$ The second line contains $k$ space-separated integers $-$ the values of $p(1) , p(2) , \cdots , p(k)$ modulo $M$ .

outputFormat: Print the answers to the test cases in the order in which they appear in the input. For each test case print a single line containing one integer: the value of $p(k + 1)$ modulo $M$ .

translation:
众所周知，斐波那契数列的公式如下：

$$F_i=\begin{cases}1&i=1\\2&i=2\\F_{i-1}+F_{i-2}&i\geqslant 3\end{cases}$$

定义 $p_i=\sum\limits_{j=1}^ka_j\times F_j^i$。现在给定 $k,m$ 以及 $\{p_i\}_{i=1}^k$，请求出 $p_{k+1}\bmod m$。

Translated by Eason_AC
2020.11.19


title: [CERC2013] Digraphs

type: P

description:
A digraph is a graph with orientation... oh, sorry, not this time. Let's stop being nerds for a minute and talk about languages (human languages, not PHP).

Digraphs are pairs of characters that represent one phoneme (sound). For example, "ch" in English (as in "church") is a single consonant sound. The languages of Central Europe are fond of digraphs: Hungarian "sz", Czech "ch" and Polish "rz" are fine examples of them.

Digraphs are very annoying for people who do not use them natively. We will make up a letter-puzzle specifically for those people. Given a list of digraphs, construct a biggest possible square of lower case English letters such that its rows and columns do not contain any of these digraphs. This means that no two consecutive letters (read from top to bottom or from left to right) can form a digraph.

inputFormat:
The first line of input contains the number of test cases $T$ . The descriptions of the test cases follow:

Each test case starts with an integer $n , 0 \le n \le 676$ , denoting the number of forbidden digraphs. The $n$ following lines contain the digraphs.

outputFormat:
For each test case print a square of the largest possible size which does not contain any of the digraphs. If it is possible to construct a square of size $20 \times 20$ or bigger, print only a $20 \times 20$ square.

Warning: Part of the example test data below was omitted for clarity. You can access full sample tests at your workstation.

translation:
## 题目描述

有一些有向字母对，构造一个尽量大（最大$20\times20$）的方阵，使得这个方阵中任意两个相邻字母对（从左到右或从上到下）都不是这些有向字母对中的一个。

## 输入格式

第一行一个整数$T$，表示数据组数。

每组数据第一行一个整数$n$($0 \le n \le 676$)，表示有向字母对数。

接下来$n$行，每行$2$个小写字母，表示一组有向字母对。

## 输出格式

对于每组数据，输出一个尽量大的方阵，不包含任何一个有向字母对（如果可以构造比$20\times20$规模更大的方阵，只需要$20\times20$规模就够了）。

如果有多组解，输出任意一组即可。

samples:
2
628
aa
az
ba
bb
bc
bd
be
bf
bg
bh
bi
bj
bk
bl
bm
bn
bo
bp
bq
br
bs
bt
bu
bv
bw
bx
by
ca
cb
cc
cd
ce
cf
cg
ch
ci
cj
ck
cl
cm
cn
co
cp
cq
cr
cs
ct
cu
cv
cw
cx
cy
da
db
dc
dd
de
df
dg
dh
di
dj
dk
dl
dm
dn
do
dp
dq
dr
ds
dt
du
dv
dw
dx
dy
ea
eb
ec
ed
ee
ef
eg
eh
ei
ej
ek
el
em
en
eo
ep
eq
er
es
et
eu
ev
ew
ex
ey
fa
fb
fc
fd
fe
ff
fg
fh
fi
fj
fk
fl
fm
fn
fo
fp
fq
fr
fs
ft
fu
fv
fw
fx
fy
ga
gb
gc
gd
ge
gf
gg
gh
gi
gj
gk
gl
gm
gn
go
gp
gq
gr
gs
gt
gu
gv
gw
gx
gy
ha
hb
hc
hd
he
hf
hg
hh
hi
hj
hk
hl
hm
hn
ho
hp
hq
hr
hs
ht
hu
hv
hw
hx
hy
ia
ib
ic
id
ie
if
ig
ih
ii
ij
ik
il
im
in
io
ip
iq
ir
is
it
iu
iv
iw
ix
iy
ja
jb
jc
jd
je
jf
jg
jh
ji
jj
jk
jl
jm
jn
jo
jp
jq
jr
js
jt
ju
jv
jw
jx
jy
ka
kb
kc
kd
ke
kf
kg
kh
ki
kj
kk
kl
km
kn
ko
kp
kq
kr
ks
kt
ku
kv
kw
kx
ky
la
lb
lc
ld
le
lf
lg
lh
li
lj
lk
ll
lm
ln
lo
lp
lq
lr
ls
lt
lu
lv
lw
lx
ly
ma
mb
mc
md
me
mf
mg
mh
mi
mj
mk
ml
mm
mn
mo
mp
mq
mr
ms
mt
mu
mv
mw
mx
my
na
nb
nc
nd
ne
nf
ng
nh
ni
nj
nk
nl
nm
nn
no
np
nq
nr
ns
nt
nu
nv
nw
nx
ny
oa
ob
oc
od
oe
of
og
oh
oi
oj
ok
ol
om
on
oo
op
oq
or
os
ot
ou
ov
ow
ox
oy
pa
pb
pc
pd
pe
pf
pg
ph
pi
pj
pk
pl
pm
pn
po
pp
pq
pr
ps
pt
pu
pv
pw
px
py
qa
qb
qc
qd
qe
qf
qg
qh
qi
qj
qk
ql
qm
qn
qo
qp
qq
qr
qs
qt
qu
qv
qw
qx
qy
ra
rb
rc
rd
re
rf
rg
rh
ri
rj
rk
rl
rm
rn
ro
rp
rq
rr
rs
rt
ru
rv
rw
rx
ry
sa
sb
sc
sd
se
sf
sg
sh
si
sj
sk
sl
sm
sn
so
sp
sq
sr
ss
st
su
sv
sw
sx
sy
ta
tb
tc
td
te
tf
tg
th
ti
tj
tk
tl
tm
tn
to
tp
tq
tr
ts
tt
tu
tv
tw
tx
ty
ua
ub
uc
ud
ue
uf
ug
uh
ui
uj
uk
ul
um
un
uo
up
uq
ur
us
ut
uu
uv
uw
ux
uy
va
vb
vc
vd
ve
vf
vg
vh
vi
vj
vk
vl
vm
vn
vo
vp
vq
vr
vs
vt
vu
vv
vw
vx
vy
wa
wb
wc
wd
we
wf
wg
wh
wi
wj
wk
wl
wm
wn
wo
wp
wq
wr
ws
wt
wu
wv
ww
wx
wy
xa
xb
xc
xd
xe
xf
xg
xh
xi
xj
xk
xl
xm
xn
xo
xp
xq
xr
xs
xt
xu
xv
xw
xx
xy
ya
yb
yc
yd
ye
yf
yg
yh
yi
yj
yk
yl
ym
yn
yo
yp
yq
yr
ys
yt
yu
yv
yw
yx
yy
za
zb
zc
zd
ze
zf
zg
zh
zi
zj
zk
zl
zm
zn
zo
zp
zq
zr
zs
zt
zu
zv
zw
zx
zy
zz
2
aa
bb

samples:
aw
wz
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa
abababababababababab
babababababababababa

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


title: [CERC2013] Bus

translation:
# [CERC2013] Bus

## 题面翻译

有一个数 $n$ ，定义一次操作为使 $n\rightarrow \frac{n-1}{2}$ 。已知经过了 $k$ 次操作后 $n$ 恰好为 $0$，求 $n$。

多测，有 $T$ 组数据，$T$ 在输入数据开头给出。

保证 $1\leqslant k\leqslant 30$。

## 题目描述

A bus with $n$ passengers opens its door at the bus stop. Exactly half of its passengers and an additional half of a passenger get out. On the next stop, again, half of the passengers plus half of a passenger leave the bus. This goes on for $k$ stops in total. Knowing that the bus leaves the last stop empty, and that no one was hurt during the trip, determine the initial number $n$ of people in the bus.

## 输入格式

The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

The only line of each test case contains the number of stops $k$, $1 \leq k \leq 30$.

## 输出格式

For each test case, output a single line containing a single integer—the initial number of bus passengers.

## 样例 #1

### 样例输入 #1

```
2
1
3
```

### 样例输出 #1

```
1
7
```

## 提示

Time limit: 1000 ms, Memory limit: 1048576 kB.

 Central Europe Regional Contest (CERC) 2013


title: [NWRRC2017] Auxiliary Project

description:
Anna has just finished her course project. She has a lot of seven-segment LED displays as leftovers and a small power source. Each display consumes power proportionally to the number of lit segments, e.g . $‘9'$ consumes twice more power than $‘7'.$

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

Anna wonders what is the maximum possible sum of digits she is able to achieve, if her power source is able to light $n$ segments, and she wants to light exactly $n$ segments.

inputFormat: The single line of the input contains one integer $n$ -- the number of segments that should be lit $(2 \le n \le 10^{6}).$

outputFormat: Output a single integer -- the maximum possible sum of digits that can be displayed simultaneously.

translation:
用 LED 显示器来表示数字，表示方法如下：

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

你必须正好点亮 $n$ 段 LED 灯，使得这些灯能够组成一些数字。现在请你求出这些一位数和的最大值。

注：“一段”LED 灯指的是一条黑色的纵向短线或一条黑色的横向线段。如，`9` 由 $6$ 断组成。

$2\le n\le2\times 10^6$。

Translated by [cmll02](https://www.luogu.com.cn/user/171487)。

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


title: [NWRRC2017] Boolean Satisfiability

description:
Boolean satisfiability problem (SAT) is known to be a very hard problem in computer science. In this problem you are given a Boolean formula, and you need to find out if the variables of a given formula can be consistently replaced by the values true or false in such a way that the formula evaluates to true. SAT is known to be NP-complete problem. Moreover, it is NP-complete even in case of $3-CNF$ formula $(3-SAT).$ However, for example, SAT problem for $2-CNF$ formulae $(2-SAT)$ is in $P$ .

$#SAT$ is the extension of SAT problem. In this problem you need to check if it is possible, and count the number of ways to assign values to variables. This problem is known to be $#P-complete$ even for $2-CNF$ formulae. We ask you to solve $#1-DNF-SAT,$ which is $#SAT$ problem for $1-DNF$ formulae.

You are given a Boolean formula in $1-DNF$ form. It means that it is a disjunction (logical or) of one or more clauses, each clause is exactly one literal, each literal is either variable or its negation (logical not).

Formally:

$〈formula〉 ::= 〈clause〉 | 〈formula〉 ∨ 〈clause〉$

$〈clause〉 ::= 〈literal〉$

$〈literal〉 ::= 〈variable〉 | ¬ 〈variable〉$

$〈variable〉 ::=$ A . . . $Z |$ a . . . $z$

Your task is to find the number of ways to replace all variables with values true and false (all occurrences of the same variable should be replaced with same value), such that the formula evaluates to true.

inputFormat: The only line of the input file contains a logical formula in $1-DNF$ form (not longer than $1000$ symbols). Logical operations are represented by $‘|'$ (disjunction) and $‘ \sim ' (negatio_n).$ The variables are $‘A'$ . . . $‘Z'$ and $‘a'$ . . . $‘z'$ (uppercase and lowercase letters are different variables). The formula contains neither spaces nor other characters not mentioned in the grammar.

outputFormat: Output a single integer -- the answer for $#SAT$ problem for the given formula.

translation:
给定一个由大小写字母（变量），``|`` 和 ``~`` 组成的布尔代数式，求对于给定的变量，有多少种方案使得给定的代数式值为 ``True`` 。

注：

``a|b`` 表示 $a\vee b$ , 也就是 C++ 中的 ``a || b`` 。

``~a`` 表示 $\neg a$，也就是 C++ 中的 ``(!a)`` 。

变量只有可能由单个字母构成。


title: [NWRRC2017] Consonant Fencity

description:
There are two kinds of sounds in spoken languages: vowels and consonants. Vowel is a sound, produced with an open vocal tract; and consonant is pronounced in such a way that the breath is at least partly obstructed. For example, letters a and $o$ are used to express vowel sounds, while letters $b$ and $p$ are the consonants (e.g . bad, pot).

a vowel (e.g . silly) or as a consonant (e.g . yellow). The letter $w$ , usually used as a consonant (e.g . wet) could produce a vowel after another vowel (e.g . growth) in English, and in some languages (e.g . Welsh) it could be even the only vowel in a word.

In this task, we consider $y$ and $w$ as vowels, so there are seven vowels in English alphabet: a , $e , i , o , u , w$ and $y$ , all other letters are consonants.

Let's define the consonant fencity of a string as the number of pairs of consecutive letters in the string which both are consonants and have different cases (lowercase letter followed by uppercase or vice versa). For example, the consonant fencity of a string CoNsoNaNts is $2$ , the consonant fencity of a string dEsTrUcTiOn is $3$ and the consonant fencity of string StRenGtH is $5$ .

You will be given a string consisting of lowercase English letters. Your task is to change the case of some letters in such a way that all equal letters will be of the same case (that means, no letter can occur in resulting string as both lowercase and uppercase), and the consonant fencity of resulting string is maximal.

inputFormat: The only line of the input contains non-empty original string consisting of no more than $10^{6}$ lowercase English letters.

outputFormat: Output the only line: the input string changed to have maximum consonant fencity.

translation:
定义**非**辅音字母为 ``a`` ``e`` ``i`` ``o`` ``u`` ``w`` ``y``。

定义一个字符串的价值是连续两个大小写不同的辅音的个数。

给定一个小写字符串，试图改变若干个字母的大小写使得这个字符串的价值最大。

输出更改后的字符串。多解任意输出。

samples: consonants CoNsoNaNts

samples: destruction dEsTrUcTiOn

samples: strength StRenGtH


title: [NWRRC2017] Dividing Marbles

description:
Debbie, Debby, Debra and Deborah are going to play a game with marbles together. Debbie has brought $2^{d_{1}}$ marbles, Debby -- $2^{d_{2}}$ marbles, Debra -- $2^{d3}$ marbles, while Deborah -- $2^{d4}$ marbles. The kids have gathered their marbles into a single pile containing $2^{d_{1}} + 2^{d_{2}} + 2^{d_{3}} + 2^{d_{4}}$ marbles, and the game is starting.

The game consists of turns. Each turn consists of two steps:

The kids choose any of their piles with more than one marble and divide it into two non-empty piles. That is, if the chosen pile contains $m \ge 2$ marbles, the new piles must contain $m_{1}$ and $m_{2}$ marbles where $m_1$ and $m_2$ are positive integers, and $m_{1} + m_{2} = m$ .

If there are several piles with the same number of marbles, only one of these piles is kept, while all the others with this number of marbles are discarded (thrown away).

The game ends when only one pile is left, and this pile contains a single marble. The goal of the game is to end it in the least possible number of turns. Note that the game is cooperative, that is, the kids aren't playing against each other, but trying to reach a common goal together.

Help the kids and find the best way to play.

inputFormat:
The first line of the input contains a single integer $T$ -- the number of test cases $(1 \le T \le 500)$ .

Each of the next $T$ lines describes one test case and contains four non-negative integers $d_{1}, d_{2}, d_{3}, d_{4} (0 \le d_{i} \le 20)$ .

outputFormat:
For each test case, output an integer $t$ -- the smallest number of turns required to end the game.

Then, output $t$ turn descriptions, in the order the turns should be made. Each description should consist of three integers $m , m_{1}, m_{2}$ -- the size of the divided pile and the sizes of the new piles, respectively $(m \ge 2$ ; $m_{1} > 0$ ; $m_{2} > 0$ ; $m_{1} + m_{2} = m)$ . Note that a pile of size $m$ must exist at that moment, and at the end of the game there should be only one pile left and that pile should contain a single marble.

translation:
**题目描述**

Debbie, Debby, Debra 和 Deborah要一起玩一个关于弹珠的游戏。Debbie 带来了  $2^{d_{1}}$ 颗弹珠, Debby 带来了  $2^{d_{2}}$ 颗弹珠, Debra 带来了  $2^{d3}$ 颗弹珠, 而 Deborah 带来了  $2^{d4}$ 颗弹珠。这些孩子们把他们的弹珠放在一起，总共有 $2^{d_{1}} + 2^{d_{2}} + 2^{d_{3}} + 2^{d_{4}}$ 颗, 游戏开始了。

游戏是多回合制。每一个回合包括两个步骤：

这些孩子们选择他们的任意一堆大于1个的弹珠然后分入两个大于0个的堆中。相当于，如果选中的那堆有 $m \ge 2$ 颗弹珠, 新的一堆必须要有 $m_{1}$ 和 $m_{2}$ 颗弹珠且 $m_1$ 和 $m_2$ 为正整数, 且 $m_{1} + m_{2} = m$.

如果有许多堆拥有同样数目的弹珠，只有一堆会被保留，其他的都会被丢弃。

当只有一堆弹珠被留下且这堆弹珠只有一颗时，游戏就结束了。游戏的目标就是用尽量少的回合让游戏结束。注意这个游戏是合作性质的，那就是，这些孩子不是互相争斗的，而是一起尝试达成同一个目标。

请帮助这些孩子找到游戏的最佳方案。

**输入格式**

第一行包括一个单独的整数，T 即测试用例的数量$(1≤T≤500)$ .

下面的每一行都描述一个测试用例且包含四个非负整数 $d_{1}, d_{2}, d_{3}, d_{4} (0 \le d_{i} \le 20)$

**输出格式**

对于每一个测试用例，输出一个整数t，即游戏结束所需的最少次数。

然后，按照回合的顺序，输出这些回合的说明。每一行说明都要包括三个整数 $ m , m_{1}, m_{2}$ 即是被分的堆和新堆的弹珠数量，依次为$(m≥2 ; m_{1} > 0; m_{2} > 0 ;  m_{1} + m_{2} = m)$

请注意大小为m的弹珠堆一定要存在，且在游戏结束时应该只剩下一堆且那一堆应该只有一颗弹珠。

**说明/提示**

时间限制: 3 s, 内存限制: 512 MB.


title: [NWRRC2017] Equal Numbers

description:
You are given a list of $n$ integers $a_{1},$ . . . , $a_{n}.$ You can perform the following operation: choose some $a_{i}$ and multiply it by any positive integer.

Your task is to compute the minimum number of different integers that could be on the list after $k$ operations for all $0 \le k \le n$ .

inputFormat: The first line of the input contains single integer $n (1 \le n \le 3·10^{5}).$ The second line of the input contains $n$ integers $a_{i} (1 \le a_{i} \le 10^{6}).$

outputFormat: Output a single line that contains $n + 1$ integers. The i-th integer should be the minimum possible number of different integers in the list after $i − 1$ operations.

translation:
给定一个长度为 $n$ 的数列 $a_1,a_2,a_3,...,a_n$，每次操作，你可以让某个被选定的数乘上任意一个正整数。

现在。对于所有的 $k\in[0,n]$，求出经过 $k$ 次操作后数列里面不同的数的数量能够达到的最小值。

Translated by Eason_AC
2020.11.15


title: [NWRRC2017] Fygon 2.0

description:
The new version of beloved programming language Fygon has been released! The brand new Fygon $2$ . $0$ still has only two statements. The first statement is lag. It substitutes almost any other statement. Second statement is a for loop:

```
for <variable> in range(<from>, <to>):
    <body>
```

The for loop makes iterate from to , both inclusive.

If is greater than , is not executed at all.

is a lowercase letter from a to $z$ , except for $n$ , which is a variable that is defined prior to the given code snippet.

and can be equal to any variable defined in outer loop. In addition to that, can be $1$ and can be $n$ .

The of the loop is indented by four spaces and contains at least one statement.

If you are familiar with Fygon $1$ . $0$ , you can notice that, in the spirit of the best programming practices, Fygon $2$ . $0$ is not backwards compatible, since the range function now requires two parameters.

The performance of the new version is significantly improved, so you can write more nested for loops. That is why we are no longer interested in the exact number of operations, but in the asymptotic complexity of the program instead. For simplicity, all for loops are nested in a single chain and there is exactly one lag statement that is inside all for loops. All loop variables are different and are not equal to $n$ .

Let's define $f(n)$ as the number of lag operations exectuted by a given Fygon program as the function of $n$ . For non-negative integer $k$ and positive rational number $C$ we say that $C · n^{k}$ is the asymptotic complexity of the program if

$$\lim_{n \to \infty}{\frac{f(n)}{C \cdot n^k}} = 1$$

Given a Fygon $2$ . $0$ program, find its asymptotic complexity.

inputFormat: The first line of the input contains single integer $m$ -- the number of lines in Fygon $2$ . $0$ program. Next $m$ lines contain the program itself. The program has at least $1$ and at most $20$ for statements. Each for statement contains either single nested for statement or lag statement.

outputFormat: Output numbers $k$ and $C$ . $C$ should be output in the form of irreducible fraction $p/q$ , where $p$ and $q$ are coprime.

translation:
卡老师新发明了一种语言：Fygon 2.0。这种语言只有两种语句：`lag` 和 `for`。其中 `for` 的格式如下：

```
for <variable> in range(<from>, <to>):
    <body>
```

- `<variable>` 是一个 `a` 到 `z` 之间的字符，但是不包括 `n`。
- `<from>` 和 `<to>` 是外面的循环中定义的变量。特别的,`<from>` 还可以是 `1`，`<to>` 还可以是 `n`。
- 这个语句表示 `<variable>` 从 `<from>` 循环到 `<to>`，两端均包含。
- 如果 `<from>` 大于 `<to>`，则该语句不会执行。
- 这里的 `<body>` 一定是一个 `for` 语句或者 `lag`，前面一定有 4 个空格的缩进。

卡老师随手写出了一个 Fygon 2.0 程序。因为他忙着去托老师的精神世界中写神题，所以这个程序的 `for` 语句数不超过 $20$ 个。

现在他想要计算这个程序的渐进时间复杂度。渐进时间复杂度定义如下：

> 定义 $f(n)$ 为 `lag` 的执行次数，若非负整数 $k$ 和正有理数 $C$ 满足
>
> $$\lim_{n\to\infty}\frac{f(n)}{C\cdot n^k}=1$$
>
> 则该程序的渐进时间复杂度为 $C\cdot n^k$。

卡老师看了一眼就算出来了，但是他想考考你，请你帮他求出这个程序的渐进时间复杂度。

samples:
4
for i in range(1, n):
    for j in range(1, i):
        for k in range(j, n):
            lag


title: [NWRRC2017] Grand Test

description:
Jeremy, Richard and James like to test cars. It is always hard for them to decide where they should do it. Usually car test looks like this. They choose a country and examine its cities and two-way roads that connect them. To perform a test, they need to choose two different cities $S$ and $F$ , such that there exist three routes between them. Moreover, each city except $S$ and $F$ should be visited by at most one route, and none of the roads may be used twice.

Then each of them takes a car in city $S$ , drives along one of those routes and tries to get to city $F$ faster than others.

You are given a description of multiple countries. For each country you should decide if it is possible to choose two cities and three routes between them in a way described above.

inputFormat:
The first line of the input contains a single integer $T$ -- number of countries $(1 \le T \le 100 000)$ . It is followed by $T$ country descriptions.

The first line of each country description contains two integers $n$ and $m$ -- the number of its cities and roads $(1 \le n , m \le 100 000)$ . The following $m$ lines contain two integer numbers each: $u_{i}$ and $v_{i}$ -- the cities at the ends of the road $(1 \le u_{i} < v_{i} \le n)$ . All roads are two-way. Each pair of cities is connected by at most one road.

Both the total number of cities and roads in all countries does not exceed $100 000$ .

outputFormat:
Output the answer for each country in the order they are given in the input.

If it is not possible to test cars in this country, the answer is $−1$ . Otherwise the first line of the answer should contain two integers $S$ and $F$ -- start and finish cities. The next three lines should contain three distinct routes. Each route is described by an integer $k$ -- the number of cities it visits, and $k$ numbers $v_{1}, v_{2}, \cdots , v_{k}$ -- the cities, where $v_{1} = S , v_{k} = F$ , and there is a road between cities $v_{i}$ and $v_{i+1}$ for all $1 \le i \le k − 1$ .

translation:
**题目描述**
给定一张 $n$ 个节点 $m$ 条边的无向图，请在图中找出两个点 $S$ 和 $F$，使得这两点间至少存在三条不相交的路径。

**输入格式**
输入的第一行包数据组数 $T(1 \leq T \leq 100000)$。对于每组数据，第一行为两个整数 $n$ 和 $m$。接下来 $m$ 行每行包含两个整数 $u$ 和 $v(1 \leq u < v \leq n)$，表示节点 $u$ 和 $v$ 之间有一条边。每对节点至多被一条边连接。保证 $\sum n$ 及 $\sum m$ 不超过 $100000$。

**输出格式**
对于每组数据，若不存在，则输出`-1`。若存在，则第一行输出 $S$ 和 $F$。接下来三行输出三条路径。每行先输出路径路径包含的点数，然后依次输出由 $S$ 到 $F$ 的路径上各点。


title: [NWRRC2017] Hidden Supervisors

description:
Helena works in a big company as a psychologist. Her task is to organize a team building game to enhance social relations between employees. Each employee except the Big boss has a single supervisor. So, employees of the company form a tree where each employee is a node, and the parent of that node is their supervisor. The root of the tree is the Big boss.

A team building game requires teams of two people. Every team should consist of an employee and their supervisor.

Helena asked every employee except the Big boss to send their supervisor ID. Some of them didn't reply. She is going to assign a fake supervisor to every employee that didn't reply, so that she could arrange as many teams as possible. And, of course, fake and real supervisors must form a tree.

Helena had a difficult, but a successful day organizing the event. Will you be able to assign fake supervisors?

inputFormat:
The first line of the input contains a single integer $n$ -- the number of employees in the company $(2 \le n \le 100 000)$ .

The following line contains $n − 1$ integers $p_{2}, p_{3},$ . . . , $p_{n},$ where $p_{i}$ is the supervisor of employee $i (0 \le p_{i} \le n)$ . If employee $i$ didn't reply to Helena, $p_{i}$ equals zero, and she needs to assign a fake supervisor to that employee. The Big boss has the number $1$ .

It's possible to assign a fake supervisor to each employee that didn't reply to Helena so that all employees will form a tree having the Big boss as a root.

outputFormat:
In the first line output a single integer $m$ -- the maximum possible number of arranged teams.

The next line should contain supervisors: $n−1$ integers, i-th of which denoting the supervisor of employee $i + 1$ (either fake or real). Of course, all real supervisors should be preserved, and employees must form a tree. It should be possible to arrange $m$ teams using specified supervisors.

translation:
## 题目简述

有一棵大小为 $n$ 的有根树，根为 $1$，其中若干结点的父亲没有确定。试求出所有可能构成的以 $1$ 为根的有根树中，最大匹配的最大值是多少，并输出构造方案。保证数据有解。

## 输入格式

第一行输入一个整数 $n$。

第二行输入 $n-1$ 个整数 $p_2,p_3,\cdots,p_n$，分别表示 $2,3,\cdots,n$ 的父亲。其中 $p_i = 0$ 表示点 $i$ 的父亲未确定，$p_i \neq 0$ 表示点 $i$ 的父亲已确定。

## 输出格式

第一行输出一个整数表示最大匹配的最大值。

第二行输出 $n-1$ 个整数 $p'_2,p'_3,\cdots,p'_n$，分别表示 $2,3,\cdots,n$ 的父亲。


title: [NWRRC2017] Intelligence in Perpendicularia

description:
There are only two directions in Perpendicularia: vertical and horizontal. Perpendicularia government are going to build a new secret service facility. They have some proposed facility plans and want to calculate total secured perimeter for each of them.

The total secured perimeter is calculated as the total length of the facility walls invisible for the perpendicularly-looking outside observer. The figure below shows one of the proposed plans and corresponding secured perimeter.

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

Write a program that calculates the total secured perimeter for the given plan of the secret service facility.

inputFormat:
The plan of the secret service facility is specified as a polygon.

The first line of the input contains one integer $n$ -- the number of vertices of the polygon $(4 \le n \le 1000)$ . Each of the following $n$ lines contains two integers $x_{i}$ and $y_{i} -$ the coordinates of the i-th vertex $(−10^{6} \le x_{i}, y_{i} \le 10^{6}).$ Vertices are listed in the consecutive order.

All polygon vertices are distinct and none of them lie at the polygon's edge. All polygon edges are either vertical $(x_{i} = x_{i+1} or$ horizontal $(y_{i} = y_{i+1})$ and none of them intersect each other.

outputFormat: Output a single integer -- the total secured perimeter of the secret service facility.

translation:
## 题目描述

给你一个数 $ n $ ，再给你 $ n $ 个点（$ x_i , y_i $），这 $ n $ 个点依次连成一个多边形。（保证多边形的每条边都与坐标轴平行或垂直，点不重合，点不在边上，边无相交）

求有多长的边是安全的？

（一个单位长度的边是安全的当且仅当它向外平移后能与其余边相遇，结合一下图看看）

## 输入格式

第一行一个数$ n $,表示有多少个定点。

接下来 $ n $ 行，行两个数 $ x_i \; y_i $ 表示每个点的坐标。

## 输出格式

一个数，表示安全的长度。


title: [NWRRC2017] Joker

description:
Joker prepares a new card trick with a strong mathematical background. You are asked to help Joker with calculations.

There is a row of $n$ cards with non-zero numbers $a_{i}$ written on them. Let's call the sum of all positive numbers $P$ and the sum of all negative numbers $N$ . Every card $i$ has a weight $w_{i} = a_{i}/P$ if $a_{i} > 0$ and $a_{i}/|N|$ otherwise.

Let's denote $s_{i} = ( \sum_{j=1}^{j \le i}{w_j})$. Joker needs to know positive $i$ with the largest $s_{i}.$ If there is more than one such $i$ , he is interested in the smallest one.

But static tricks are boring, so Joker wants to change numbers on some cards, and after each change he needs to known where is the largest $s_{i}$ is.

inputFormat:
The first line of the input contains two integers $n$ and $m$ -- the number of cards and the number of changes $(1 \le n , m \le 50 000)$ .

The second line consists of $n$ integers $a_{i}$ -- numbers written on cards at the beginning $(−10^{9} \le a_{i} \le 10^{9}; a_{i} ≠ 0)$ .

The following $m$ lines contain two integers each: $p_{i}$ and $v_{i},$ that means value of card at position $p_{i}$ is changed to $v_{i} (1 \le p_{i} \le n$ ; $−10^{9} \le v_{i} \le 10^{9}; v_{i} ≠ 0)$ .

It is guaranteed that at each moment there is at least one card with positive number and at least one card with negative number. The sum of all positive cards will never exceed $10^{9}$ and the sum of all negative cards will never exceed $−10^{9}.$

outputFormat: You should output $m+1$ integers. The first integer is the position of the largest $s_{i}$ for the initial numbers. Next $m$ numbers are positions of the largest $s_{i}$ after each change.

translation:
有一个长度为 $n$ 的数列，第 $i$ 个元素的值为 $a_i$，定义 $P$ 为数列中所有正整数的和，$N$ 为所有负整数的和。定义一个元素的重要值 $w_i=\begin{cases}\dfrac{a_i}{P}&a_i>0\\\dfrac{a_i}{|N|}&\text{otherwise}\end{cases}$，并定义 $s_i$ 为前 $i$ 个元素的重要值之和，即 $\sum\limits_{j=1}^iw_j$。

请先求出当前数列中使 $s_i$ 最大的 $i$。然后有 $m$ 次操作，每次操作将某个元素改成一个给定的值，请在每次操作后求出当数列中使 $s_i$ 最大的 $i$。

如果有多个满足要求的 $i$，则答案取最小的。

Translated by Eason_AC
2020.11.15


title: [NWRRC2017] Kotlin Island

description:
There is an urban myth that Peter the Great wanted to make a rectangular channel-grid engineering masterpiece not only from Vasilyevskiy island, but also from Kotlin island (where the town of Kronstadt is located nowadays).

The following mathematical model was (allegedly) presented to the tsar. The island is considered a rectangular grid $h$ cells high and $w$ cells wide. Each cell is dry land initially but can become water.

Technologies of those days allowed engineers to dig a channel across the entire island. In that case an entire row or an entire column of cells became water. If some of these cells already were water, their status did not change.

Your task is to propose a plan of the island which has exactly $n$ connected components of dry land cells.

inputFormat: The only line of the input contains three integers $h , w$ , and $n$ -- grid's height, width and the desired number of connected components $(1 \le h , w \le 100$ ; $1 \le n \le 10^{9}).$

outputFormat:
If there is no valid plan containing $n$ connected components, output a single word `Impossible`.

Otherwise output $h$ lines of length $w$ depicting the plan. Dot $(‘. ')$ represents a dry land cell, hash $(‘#')$ represents a water cell.

translation:
对于一个 $h$ 行 $w$ 列的网格，每个格子都是“干燥的”。

你的每次操作可以把某一行或某一列的所有格子变成“湿润的”。

你的目标是在网格上留下**恰好** $n$ 个由“干燥的”格子形成的连通块。

如果可以实现，请你输出一个 $h$ 行 $w$ 列的矩阵。
其中，用 `.` 表示“干燥的”格子， `#` 表示“湿润的”格子。

否则，输出一行一个 `Impossible` 表示不可能实现目标。

samples:
5 3 10
Impossible


title: [NWRRC2017] Little Difference

description:
Little Lidia likes playing with numbers. Today she has a positive integer $n$ , and she wants to decompose it to the product of positive integers.

Because Lidia is little, she likes to play with numbers with little difference. So, all numbers in decomposition should differ by at most one. And of course, the product of all numbers in the decomposition must be equal to $n$ . She considers two decompositions the same if and only if they have the same number of integers and there is a permutation that transforms the first one to the second one.

Write a program that finds all decompositions, which little Lidia can play with today.

inputFormat: The only line of the input contains a single integer $n (1 \le n \le 10^{18}).$

outputFormat: In first line output the number of decompositions of $n$ , or $−1$ if this number is infinite. If number of decompositions is finite, print all of them one per line. In each line first print number $k_{i}$ of elements in decomposition. Then print $k_{i}$ integers in this decomposition in any order. Don't forget that decompositions which are different only in order of elements are considered the same.

translation:
小刘烨喜欢玩数字，她有一个正整数$n$，她想把它分解成正整数的乘积，她喜欢玩没有什么区别的数字。因此，分解中的所有数字应该最多相差1，
而且，分解中所有数字的乘积必须等于$n$，她认为两个分解是相同的，当且仅当它们有相同数量的整数，并且有一个排列将第一个转化为第二个，写一个程序，找出小刘烨今天可以玩的所有的分解。

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

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


title: [NWRRC2016] Anniversary Cake

description:
Two students, Adam and Anton, are celebrating two-year anniversary of not passing their Math $Logic exa_m.$ After very careful search in a local supermarket, they bought a rectangular cake with $integer dimensions$ and two candles.

Later in the campus Adam put the candles into different integer points of the cake and gave a knife $to Anto_n$ to cut the cake. The cut should start and end at integer points at the edges of the cake, and $it should$ not touch the candles. Also each piece should have exactly one candle at it. Please, help $Anto_n to$ find the starting and ending points of the cut.

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

A $7 \times 3$ cake and two candles at $(2 , 2)$ and $(3 , 2)$ .

Anton can cut this cake through $(0 , 0)$ and $(4 , 3)$ .

inputFormat: The single line of the input contains six integers: $w , h$ -- cake dimensions; $a_{x}, a_{y}$ -- $x$ and $y coordinates$ of the first candle; $b_{x}, b_{y}$ -- the coordinates of the second candle $(3 \le w , h \le 10^{9}; 0 < a_{x}, b_{x} < w$ ; $0 < a_{y}, b_{y} < h$ ; $a_{x} ≠ b_{x}$ or $a_{y }≠ b_{y}).$

outputFormat:
Output four integers $s_{x}, s_{y}, e_{x},$ and $e_{y}$ -- the starting and ending coordinates of the cut. Both $starting and$ ending point of the cut should belong to the sides of the cake.

If there are several solutions, output any of them.

translation:
有一个长方形蛋糕和两个蜡烛，蛋糕的尺寸是整数。

把两个蜡烛放在蛋糕的不同整数点上，并用一把刀来切蛋糕。切割应该在蛋糕边缘的整数点开始和结束，并且不应该接触蜡烛。此外，每件作品都应该有一支蜡烛。请找到切入的起点和终点。

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

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


title: [NWRRC2016] Boys and Girls

description:
Bob found a nice task in his old math book for children. It says:

There are $10$ children standing in a circle, $5$ of them stand next to a boy, and $7$ of them stand next to a girl. How is it possible?

Here is the solution to the task. If $4$ boys and $6$ girls stand like this: BGBGBGBGGG, there are $5$ children who stand next to a boy (here they are underlined: BGBGBGBGGG), and $7$ children who stand next to a girl $(BGBGBGBGGG).$

Now Bob wants to solve a generalized version of this task:

There are $n$ children standing in a circle, $x$ of them stand next to a boy, and $y$ of them stand next to a girl. How is it possible?

Help Bob by writing a program that solves the generalized task.

inputFormat: The single line of the input contains three integers $n , x$ and $y (2 \le n \le 100 000$ ; $0 \le x , y \le n)$ .

outputFormat:
If there is a solution, output a string of length $n$ , describing the order of children in the circle. $Character ‘G'$ corresponds to a girl, character $‘B'$ corresponds to a boy. If there are several solutions, output any $of the_m.$

If there is no solution, output `Impossible`.

translation:
### 题目描述

Bob在他那本给孩子们的旧数学书中找到了一个好任务。上面写着：

有 $10$ 个孩子站成一个圆圈，其中 $5$ 个站在一个男孩旁边， $7$ 个站在一个女孩旁边。如何解决这个任务？

这个任务的解决方案如下：如果 $4$ 个男孩和 $6$ 个女孩像这样站着：$bgbgbbggg$，那么有 555 个孩子站在一个男孩旁边（用粗体字标记：b**g**b**g**b**g**b**g**g**g**）， 777 个孩子站在一个女孩旁边（用粗体字标记：**b**g**b**g**b**g**bggg**）。

现在Bob想解决这个任务的广义版本：

有 $n$ 个孩子站在一个圆圈里，其中 $x$ 个孩子站在一个男孩旁边， $y$ 个孩子站在一个女孩旁边。如何解决这个任务？

请编写一个程序来帮助Bob解决这个任务。

### 输入格式
一行，包括三个整数 $n$ , $x$ , $y$ 。($2≤n≤100000$; $0≤x,y≤n$)

### 输出格式
若有解，输出一个长度为 $n$ 的字符串，描述圆中元素的顺序。每个字符 $G$ 对应一个女孩，字符 $B$ 对应一个男孩。如果有多个解决方案，则输出其中任意一种。
如果没有解决方案，输出```'Impossible'```
。（不包括引号）

samples:
10 5 7
BGBGBGBGGG

samples:
10 3 8
Impossible

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


title: [NWRRC2016] CodeCoder vs TopForces

description:
Competitive programming is very popular in Byteland. In fact, every Bytelandian citizen is registered at two programming sites -- CodeCoder and TopForces. Each site maintains its own proprietary rating system. Each citizen has a unique integer rating at each site that approximates their skill. Greater rating corresponds to better skill.

People of Byteland are naturally optimistic. Citizen A thinks that he has a chance to beat citizen B in a programming competition if there exists a sequence of Bytelandian citizens $A = P_{0}, P_{1},...,P_{k} = B$ for some $k \ge 1$ such that for each $i (0 \le i < k) , P_{i}$ has higher rating than $P_{i+1}$ at one or both sites.

Each Bytelandian citizen wants to know how many other citizens they can possibly beat in a programming competition.

inputFormat: The first line of the input contains an integer $n$ -- the number of citizens $(1 \le n \le 100 000)$ . $The following n$ lines contain information about ratings. The i-th of them contains two integers $CC_{i} and TF_{i}$ -- ratings of the i-th citizen at CodeCoder and TopForces $(1 \le CC_{i}, TF_{i} \le 10^{6}).$ All the ratings at each site are distinct.

outputFormat: For each citizen $i$ output an integer $b_{i}$ -- how many other citizens they can possibly beat in a programming competition. Each $b_{i}$ should be printed in a separate line, in the order the citizens are given in the input.

translation:
- 有 $n$ 个人，每个人有两个能力值 $CC_i$ 和 $TF_i$。第 $i$ 个人能打败第 $j$ 个人当且仅当 $CC_i >CC_j$ 或 $TF_i>TF_j$。

- 强的关系具有传递性，也就是说 $i$ 比 $j$ 强，$j$ 比 $k$ 强，那么 $i$ 比 $k$ 强。 求出每个人最多可以打败的人的个数。

- $n \leq10^5$，$CC_i,TF_i \leq10^6$，数据保证 $CC_i$ 两两不同、$TT_i$ 两两不同。


title: [NWRRC2016] Digital Addition

description:
Deidra is doing a columnar addition. She writes down two non-negative integer summands one below the other, left-pads them with zeroes so that they have equal length, and calculates the sum (e.g. $ 77 + 05 = 82$) . If the sum is longer than each of the summands (because of a carry, as in $96 + 07 = 103$) she appends a zero at the beginning of each summand ($096 + 007 = 103)$ . She allows herself to use unnecessary leading zeroes ( $007 + 004 = 011)$ as soon as the length of all three numbers is the same.

Also Deidra has a homemade printing press. She decided to print her addition without a plus or $a horizontal$ line, using the following standard font:

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

Unfortunately, she messed up with spacing, and all the digits were printed over each other in the following way. Digits that were supposed to be horizontally adjacent were printed so that the right two segments of the left digit coincide with the left two segments of the right digit. Digits that were supposed to be vertically adjacent were printed so that the bottom half (a square with 4 segments) of the upper digit coincides with the top half of the lower digit.

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

When one or more black segments are printed at the same position, the result looks black. When only empty segments are printed at the position, the result looks white.

Given the resulting picture, find a correct addition that could produce it or detect that there is none.

inputFormat:
The first line of the input contains an integer $w (1 \le w \le 100)$ -- the width of Deidra's addition $(number of$ digits in each line).

The following $9$ lines contain the description of the picture printed with the bad spacing. Each line contains $w$ or $w + 1$ digits. ‘1' denotes a black segment, ‘0' denotes a white one. Even lines start with a space. See the examples for clarification.

outputFormat:
If there is no valid addition, output `NO`.

Otherwise output a valid addition that produces the given figure. The output should consist of three lines, each containing $w$ digits.

If there are several solutions, output any of them.

translation:
Deidra正在做一个列式的加法。她写下两个正整数来对其进行求和，且一个在另一个下方，在它们的左边添0，使得他们拥有相同的长度，然后相加计算结果（例如 $77 + 05 = 82$）。如果这个结果的长度大于这两个加数任何一个的长度（由于进位，例如$96 + 07 = 103$），就在两个加数前面附加零（$096 + 007 = 103$）。她允许不必要的前导零的出现（$007 + 004 = 011$）只要算式中的三个数字的长度都相同。

Deidra还有一台自制的打印机。她决定在没有加号和水平线的情况下打印她的加法算式，使用下面的标准字体
![](https://onlinejudgeimages.s3.amazonaws.com/problem/13476/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7%202016-11-01%20%EC%98%A4%ED%9B%84%202.41.11.png)

不幸的是，她弄乱了这些数字的间距，所有的数字都将以以下方式打印。打印这些本应水平相邻的数字时左边数字的右两段与右边数字的左两端重合。打印应该竖直相邻的数字时，上边数字的下半部分（由四段组成的正方形部分）与下边数字的上半部分重合。

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

如果在同一位置打印一个或多个线段时，将显示为黑色。当所在位置仅打印空段时，将显示为白色。

给定一个生成的图片，找到可以通过打印机产生这个图片的正确算式。如果找不到符合要求的算式，就输出 `NO`

## 输入格式
第一行包含一个整数$w$$(1\le w \le 100)$ 代表Deidra加法的宽度（接下来每行的数字个数）

接下来的$9$行包含对于用错误打印机输出的图片的描述。每行包含$w$或$w+1$个数字。"1"表示黑色段，"0"表示白色段。偶数行以空格开头。有关说明请参阅样例。

## 输出格式

如果没有符合要求的算式，则输出 `NO` 。

否则输出给定图片所对应的有效算式。输出应由三行组成，每行包含$w$个数字。

如果有多个符合规定的算式，请输出其任何一个。


title: [NWRRC2016] Easy Reading

description:
Eugene is reading a boring book. To make this process interesting he is drawing a picture at the  same time.  He has a piece of graph paper that is divided into square cells. All the cells are empty at  the beginning.

Eugene starts by painting over one cell. Then he opens the book at a random page and starts reading.   Whenever  he sees the letter  `u`  in the text, he moves his pen one cell up and then paints over the  cell under  his pen. Whenever he sees the letter  `d`,  he does the same but moves his pen one cell down  instead of  up. For letters  `l`  and  `r`  he moves to the left and to the right, respectively. If he wants to paint  a cell  that was already painted, he paints it again.

You have found a piece of paper and the text of the book. Now you want to understand if the picture  o_n the  paper could be drawn by Eugene at some point of his book reading. Remember that Eugene  could use  some substring of the text.

inputFormat:
The first line of the input contains an integer $l$ -- the length of the text $(1 \le l \le 100 000)$ . The $second line$ contains a string of length $l$ -- the text. It contains only lowercase English letters, spaces, commas and periods. The text neither begins nor ends with a space.

The third line contains two positive integers $n$ and $m$ -- the picture dimensions $(2 \le n \times m \le 100 000)$ .

Each of the following $n$ lines contains a string of length $m$ . Painted cells are denoted by `X`, while empty cells -- by `.` . It is guaranteed that there are at least two painted cells in the picture.

The first of these $n$ lines corresponds to the top of the picture and the last one corresponds to the bottom of it.

outputFormat:
If the picture could be painted by Eugene, output `YES` on the first line. On the second line print two integers b and $e$ such that if Eugene read all letters from $b$ to $e$ , inclusive, he would draw exactly $the same$ picture as described in the input $(1 \le b \le e \le l)$ . If there are several solutions, output any of them.

If the picture couldn't be drawn by Eugene, output `NO`.

translation:
## 题目描述

Eugene正在读一本无聊的书。为了使阅读更有趣，他在阅读的同时同时作画。 他有一张方格纸。 所有的方格一开始都是空的。

Eugene一开始在一个方格上作画。让后他随机翻开一页并开始阅读。当他遇到字母 `u`  时, 他把笔向上移动一格并在这格上画画。 当他看到 `d`时, 他会做同样的操作，但是向下移动一格而不是向上移动一格。 `l` ,`r`分别是向左和向右一格。 如果这个单元格已经画过了他会再画一次。

现在你有一张纸与这本书中的内容。 现在你想知道这张纸上的图片是否可能被Eugene在某一时刻画过。 记住：Eugene可以只使用用这个内容的子字符串。

## 输入格式

第一行是一个整数$l(1 \le l \le 10^5)$--表示这个内容的长度。

第二行是一个长度为$l$的字符串$a$。它只包含小写英文字母、空格、逗号和句号。$a$既不会以空格开头也不会以空格结尾。

第三行是两个整数$n$ 与 $m$--图的大小$(2 \le n \times m \le 10^5)$ 。

第$4$~$3+n$行，每行一个长度为$m$的字符串。画过的格子用`x`表示，没画过的用`.`表示。保证一幅图中至少有两个格子已被涂色。

这 $n$ 行字符串中的第一行对应于图片的顶部，最后一行对应于图片的底部。

## 输出格式

如果可能被绘制，第一行输出`YES`，第二行输出用空格隔开的两个整数$b$和$e$,表示Eugene从第$b$个字母开始读，到第$e$个字母结束(包含$b$和$e$)。

如果不能，输出`NO`。

## 样例 #1

### 样例输入 #1

```
43
you should read statement really carefully.
3 6
...XX.
..XXX.
...XXX
```

### 样例输出 #1

```
YES
3 42
```

## 样例 #2

### 样例输入 #2

```
43
you should read statement really carefully.
3 2
XX
XX
XX
```

### 样例输出 #2

```
NO
```

## 说明/提示

时限: 2 s, 内存限制: 256 MB.


title: [NWRRC2016] Folding

description:
As you can remember, Alex is fond of origami. She switched from squares to rectangles, and rectangles are much more difficult to master. Her main interest is to determine what is the minimum possible number of folds required to transform $W \times H$ rectangle to $w \times h$ one. The result of each fold should also be rectangular, so it is only allowed to make folds that are parallel to the sides of the rectangle.

Help Alex and write a program that determines the minimum required number of folds.

inputFormat: The first line of the input contains two integers $W$ and $H$ -- the initial rectangle dimensions. The second line contains two more integers $w$ and $h$ -- the target rectangle dimensions $(1 \le W , H , w , h \le 10^{9}).$

outputFormat:
Output a single integer -- the minimum required number of folds to transform the initial rectangle to the target one.

If the required transformation is not possible, output $−1$ .

translation:
### 题目大意：

求一个 $W\times H $ 的矩形通过折叠变为一个 $w\times h$ 的矩形的最少折叠次数，其中每次折叠的折痕必须平行于矩形的一边。

------------

### 输入格式：

第一行两个正整数 $W,H$，第二行两个正整数 $w,h$。

$1\le W,H,w,h\le10^9$

------------

### 输出格式：

输出最少折叠次数。若无法通过折叠变为目标矩形，输出 `-1`。


title: [NWRRC2016] Gangsters in Central City

description:
For a long time, there were no problems with water in Central City. The sewage of the city has a form of a rooted tree: the central reservoir is situated at the root and the houses are at the leaves. The water flows from the central reservoir to the houses by the pipes that runs along the edges of the tree. Each house has an access to water.

Suddenly, gangsters captured some of the houses. As a mayor of the city you are very concerned, and you want to kick out the gangsters. So you want to stop the water flow to houses captured by the gangsters.  To do that you could clog some pipes of the sewage system. If the path from the reservoir to a house contains at least one clogged pipe, the house does not have an access to water.

You are very afraid of the gangsters, so you decided to clog up the minimal number of pipes, that it could look like an accident. At the same time, you care about the citizens, so for the chosen number of clogged pipes, you want to minimize the number of houses without gangsters and access to water.

Unfortunately, the gangsters could appear and disappear from some houses. So, you are asking the scientists about the minimum required number of clogged pipes and the minimum required number of houses without gangsters and access to water after each change in the gangsters' location.

inputFormat:
The first line of the input contains two integers $n$ and $q$ -- the number of vertices in the tree which represents the sewage and the number of changes in the location of the gangsters $(2 \le n \le 100 000$ ; $1 \le q \le 100 000)$ .

The second line contains the description of the sewage: a sequence of $n − 1$ integers $p_{2}, p_{3},$ . . . , $p_{n}$, where $p_{i} is$ the parent of the vertex $i (1 \le p_{i} < i)$ . The central reservoir is located at the vertex $1$ .

The next $q$ lines represent the changes in the location of the gangsters. Each change could be one of two different types:

- `+ v` -- the gangsters capture the house at vertex $v$ ;
- `- v` -- the gangsters leave the house at vertex $v$ .

At the beginning all the houses are free of gangsters. All the changes form the correct sequence: the gangsters cannot capture the house if it is already captured and the gangsters could not leave the house if it is not captured.

outputFormat:
The output should contain 2q integers, two in each line: $c_{i}$ -- the minimum number of clogged pipes and $h_{i}$ -- the minimum number of houses without gangsters and have no access to water for the chosen $c_{i}$

.

translation:
给出一棵含有 $n$ 个节点的，且 $1$ 为根节点的树，叶子节点都是房屋，让你在一个集合里面进行添加房屋和移除房屋的操作。

每一次添加和移除后，你将要回答下面两个问题：

1.  最少需要砍多少条边，才能使已选房屋都不能从根节点到达。

2.  在第 $1$ 问的条件下，如何砍边使从根节点点开始走不能到达的非已选房屋数目最小，输出最小值。


title: [NWRRC2016] Hard Cuts

description: Given a rectangle with integer side lengths, your task is to cut it into the smallest possible number $of squares$ with integer side lengths.

inputFormat: The first line contains a single integer $T$ -- the number of test cases $(1 \le T \le 3600)$ . Each of the $next T$ lines contains two integers $w_{i}, h_{i}$ -- the dimensions of the rectangle $(1 \le w_{i}, h_{i} \le 60$ ; for any $i ≠ j, either w_{i }≠ w_{j}$ or $h_{i} ≠ h_{j} ).$

outputFormat: For the i-th test case, output $k_{i}$ -- the minimal number of squares, such that it is possible to cut $the w_{i}$ by $h_{i}$ rectangle into $k_{i}$ squares. The following $k_{i} lines$ should contain three integers each: $x_{ij} , y_{ij} -- the$ coordinates of the bottom-left corner of the j-th square and $l_{ij }--$ its side length $(0 \le x_{ij} \le w_{i} − l_{ij} ; 0 \le y_{ij} \le h_{i} −l_{ij} ).$ The bottom-left corner of the rectangle has coordinates $(0 , 0)$ and the top-right $corner has$ coordinates $(w_{i}, h_{i}).$

translation:
# 题目描述
给定一个边长为整数的矩形，您的任务是将其切割成边长为整数的正方形的尽可能少的正方形。


title: [NWRRC2016] Integral Polygons

description:
Ingrid holds a polygon shop in a far away country. She sells only convex polygons with integer coordinates. Her customers prefer polygons that can be cut into two halves in a proper way, that is the cut should be straight  with starting and ending points in the polygon vertices and both halves should be non-empty and have integer areas. The more ways to cut the polygon in the proper way are -- the more expensive the polygon is.

For example, there are three ways to cut the left polygon in the proper way, and two ways for the right polygon.

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

The polygons in the shop are always of excellent quality, so the business is expanding. Now Ingrid needs some automatic tool to determine the number of ways to cut the polygon in the proper way. This is very important for her shop, since otherwise you will spend a lot of time on setting prices -- just imagine how much time would it take to set prices for a medium-sized van with polygons. Could you help Ingrid and write the tool for her?

inputFormat: The first line of the input contains an integer $n$ -- the number of polygon vertices $(4 \le n \le 200 000)$ . $ Each$ of the following $n$ lines contains vertex coordinates: a pair of integers $x_{i}$ and $y_{i}$ per line $(-10^{9} \le x_{i}, y_{i} \le 10^{9}).  The$ specified polygon is convex and its vertices are specified in the order of traversal.

outputFormat: Output a single integer $w$ -- the number of ways to cut the polygon in the proper way.

translation:
按顺序给定一个凸多边形的  $n$ 个定点  $(x_i,y_i)$ ， $x_i,y_i\in[-10^9,10^9]$ 且为整数。

求满足条件的对角线数量，使得该对角线将多边形分成的两个部分的面积皆为整数。


title: [NWRRC2016] Java2016

description:
John likes to learn esoteric programming languages. Recently he discovered the probabilistic $\textit{programming language}$ Java2K. Built-in functions of Java2K have only a certain probability to do whatever you $\textit{intend them}$ to do.

The Java2K programming is very hard, so John designed a much simpler language for training: Java2016. $\textit{Built-in}$ operators of Java2016 are deterministic, while their operands are random. Each value in $\textit{Java2016 is}$ a positive integer in the range $0 \cdots 255$ , inclusive.

Java2016 supports six operators of three precedencies:

$$\begin{aligned}{\langle \mathrm{expression}\rangle}&\quad::=\quad{\langle \mathrm{expression}\rangle}\operatorname{`\texttt{min}\text'}{\langle \mathrm{sum}\rangle}\mid{\langle \mathrm{expression}\rangle}\operatorname{`\texttt{max}\text'}{\langle \mathrm{sum}\rangle}\mid {\langle \mathrm{sum}\rangle}\\{\langle \mathrm{sum}\rangle}&\quad::=\quad{\langle \mathrm{sum}\rangle}\operatorname{`\texttt{+}\text'}{\langle \mathrm{term}\rangle}\mid{\langle \mathrm{sum}\rangle}\operatorname{`\texttt{-}\text'}{\langle \mathrm{term}\rangle}\mid{\langle \mathrm{term}\rangle}\\{\langle \mathrm{term}\rangle}&\quad::=\quad{\langle \mathrm{term}\rangle}\operatorname{`\texttt{*}\text'}{\langle \mathrm{factor}\rangle}\mid {\langle \mathrm{term}\rangle}\operatorname{`\texttt{/}\text'}{\langle \mathrm{factor}\rangle}\mid {\langle \mathrm{factor}\rangle}\\{\langle \mathrm{factor}\rangle}&\quad::=\quad\operatorname{`\texttt{(}\text'}{\langle \mathrm{expression}\rangle}\operatorname{`\texttt{)}\text'}\mid `\texttt{?}\text'\mid {\langle \mathrm{macro}\rangle}\end{aligned}$$

Minimum $(\textit{`min'})$ and maximum $((\textit{`max'}))$ operators are defined as usual. Addition $(\text{`+'}),$ subtraction $(\text{`--'}) and$ multiplication $(\text{`}\times\text{'})$ are defined modulo $256$ . The result of the division $(\text{`}/\text{'})$ is rounded towards zero. $\textit{If}$ the divider is zero, the program crashes. The argument of the operator is a result of another $\textit{operator, evenly}$ distributed random value $(\text{`}?\text{'})$, or macro substitution.

For instance, the probability that $\text{`?/?/?'}$ is evaluated to zero is $98.2\%$, while the probability of $the crash$ is $0.8\%$.

The Java2016 program consists of zero or more macro definitions, followed by the resulting expression. $ Each$ macro definition has a form of

$$\begin{aligned}{\langle \mathrm{macrodef}\rangle}&\quad::=\quad{\langle \mathrm{macro}\rangle}\operatorname{`\texttt{=}\text'}{\langle \mathrm{expression}\rangle}\\{\langle \mathrm{macro}\rangle}&\quad::=\quad\operatorname{`\texttt{a}\text'}\ldots\operatorname{`\texttt{z}\text'}\end{aligned}$$

The macro should be defined before the first use. It may not be redefined. The macro is expanded to $its definitio_n$ on each use. For instance,

```plain
a = ? max ?
(a max $a) / a
```

is expanded to `((? max ?) max (? max ?)) / (? max ?)`.

John is going to add probabilistic constants to Java2016, so for each possible constant value he needs $a progra_m$ that successfully evaluates to this value with at least one-half probability. Crashes are $\textit{counted toward}$ failures.

inputFormat: The input contains a single integer $c$ -- the target constant $(0 \le c \le 255)$ .

outputFormat: Output a Java2016 program that successfully evaluates to constant $c$ with probability no less than $1/2$ . $ The$ total length of the program should not exceed $256$ characters (excluding spaces).

translation:
John 喜欢学习深奥的编程语言。最近，他发现了概率编程语言 Java2K。Java2K 的内置函数只有一定的概率去执行你想让它们做的事情。

Java2K 编程非常困难，因此 John 设计了一种简单得多的语言用于训练：Java2016。Java2016 的内置运算符是确定性的，而它们的操作数是随机的。Java2016 中的每个值都是 $0$ 到 $255$ (包含 $0$ 和 $255$) 中的整数。

Java2016 支持分为三个优先级的六种运算符：

$$\begin{aligned}{\langle \mathrm{expression}\rangle}&\quad::=\quad{\langle \mathrm{expression}\rangle}\operatorname{`\texttt{min}\text'}{\langle \mathrm{sum}\rangle}\mid{\langle \mathrm{expression}\rangle}\operatorname{`\texttt{max}\text'}{\langle \mathrm{sum}\rangle}\mid {\langle \mathrm{sum}\rangle}\\{\langle \mathrm{sum}\rangle}&\quad::=\quad{\langle \mathrm{sum}\rangle}\operatorname{`\texttt{+}\text'}{\langle \mathrm{term}\rangle}\mid{\langle \mathrm{sum}\rangle}\operatorname{`\texttt{-}\text'}{\langle \mathrm{term}\rangle}\mid{\langle \mathrm{term}\rangle}\\{\langle \mathrm{term}\rangle}&\quad::=\quad{\langle \mathrm{term}\rangle}\operatorname{`\texttt{*}\text'}{\langle \mathrm{factor}\rangle}\mid {\langle \mathrm{term}\rangle}\operatorname{`\texttt{/}\text'}{\langle \mathrm{factor}\rangle}\mid {\langle \mathrm{factor}\rangle}\\{\langle \mathrm{factor}\rangle}&\quad::=\quad\operatorname{`\texttt{(}\text'}{\langle \mathrm{expression}\rangle}\operatorname{`\texttt{)}\text'}\mid `\texttt{?}\text'\mid {\langle \mathrm{macro}\rangle}\end{aligned}$$

最小 ($\operatorname{`\texttt{min}\text'}$) 和最大 ($\operatorname{`\texttt{max}\text'}$) 运算符的定义和通常一样。加法 ($\operatorname{`\texttt{+}\text'}$)、减法 ($\operatorname{`\texttt{-}\text'}$) 和乘法 ($\operatorname{`\texttt{*}\text'}$) 是在模 $256$ 的意义下定义的。除法 ($`\operatorname{\texttt{/}\text'}$) 的结果向 $0$ 取整。如果除数是 $0$，程序就会崩溃。运算符的参数是另一个运算符的结果、均匀分布的随机数 ($\operatorname{`\texttt{?}\text'}$) 或宏代换的结果。

例如，$``\texttt{?/?/?}\text{''}$ 有 $98.2\%$ 的概率计算得到 $0$，而崩溃的概率为 $0.8\%$。

Java2016 程序由零个或多个宏定义以及随后的结果表达式组成。每条宏定义都形如

$$\begin{aligned}{\langle \mathrm{macrodef}\rangle}&\quad::=\quad{\langle \mathrm{macro}\rangle}\operatorname{`\texttt{=}\text'}{\langle \mathrm{expression}\rangle}\\{\langle \mathrm{macro}\rangle}&\quad::=\quad\operatorname{`\texttt{a}\text'}\ldots\operatorname{`\texttt{z}\text'}\end{aligned}$$

宏必须在第一次使用前被定义。宏不能被重复定义。宏在每次使用时都会被展开成它的定义。例如，

$$\texttt{a = ?  max ?}\\\texttt{(a max a) / a}$$

会被展开成 $``\texttt{((? max ?) max (? max ?)) / (? max ?)}\text{''}$。

John 将要把概率常量加入 Java2016，因此对每个可能的常量，他需要一个程序能以至少一半的概率成功计算出这个值。崩溃被算作失败。

#### 输入

输入包含一个整数 $c$ ($0\le c\le 255$)，表示目标常量。

#### 输出

输出一个 Java2016 程序，它需要能够以至少 $1/2$ 的概率成功计算出常量 $c$。程序的总长度不应超过 $256$ 个字符 (空格不计算在内)。

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


title: [NWRRC2016] King’s Heir

description:
The king is dead, long live the king! After the sudden death of the king Fert XIII the people of the Flatland Kingdom are going to welcome the new king. Unfortunately, there is a problem, Fert has too many sons.

Actually, he has $n$ sons and he loved each new son more than all of his previous sons. Well, probably he just stopped loving his sons because of their bad behavior. Anyway, after the new son was born Fert made the new testament that declared that the newly born son would be the heir.

However, there is a problem. Only the king's son who is at least $18$ years old at the moment of the $king's death$ can become a new king. Now the ministers of the government are trying to find the correct $new king,$ but they seem to fail. Help them!

inputFormat:
The first line of the input contains three integers: $d , m$ and $y$ -- the day, the month and the year of the king's death, $d$ is from $1$ to $31$ , $m$ is from $1$ to $12 , y$ is from $1$ to $9999$ . It is guaranteed that there exists day $d$ in month $m$ , all months have the same number of days in Flatland as in our country, except that Flatland calendar doesn't have leap years, so February (month $2$) always has $28$ days.

The second line contains $n (1 \le n \le 100)$ -- the number of king's sons. The following $n$ lines contain three integers each $d_{i}, m_{i}$ and $ y_{i}$ and specify the birth dates of king's sons. All dates are correct and no son is born after or on the day of king's death. The king had no twins, so no two sons were born on the same date.

outputFormat: Output one integer -- the number of the son that would become the king, or $−1$ if none of them is $at least 18$ years old. The sons are numbered from $1$ to $n$ in order they are described in the input. The youngest son who is at least $18$ years old at the moment of the king's death would become the king. $If the$ son has his 18th birthday exactly on the day of the king's death, he can become a king.

translation: 在国王去世的那一天，国王会让年龄最小但已满十八周岁的儿子继承国王，求哪一个儿子继承了国王，若没有儿子满足条件，则输出`-1`。保证国王不会有双胞胎。


title: [NWRRC2015] Alex Origami Squares

description: Alex is fond of origami -- Japanese art of paper folding. Most origami designs start with a square sheet of paper. Alex is going to make a present for his mother. Present's design requires three equal square sheets of paper, but Alex has only one rectangular sheet. He is able to cut out squares of this sheet, but their sides should be parallel to the sides of the sheet. Help Alex to determine the maximum possible size of the paper squares he is able to cut out.

inputFormat: The single line of the input file contains two integers $h$ and $w$ -- the height and the width of the sheet of paper $(1 \le h , w \le 1000)$ .

outputFormat:
Output a single real number -- the maximum possible length of the square side. It should be possible to cut out three such squares of $h \times w$ sheet of paper, so that their sides are parallel to the sides of the sheet.

Your answer should be precise up to three digits after the decimal point.

translation:
## 题目描述

有一张矩形纸，要求将其裁成三个全等的正方形，且每一个正方形的侧面都与纸张的侧面平行，问裁成的小正方形边长最大是多少。

## 输入格式

一行两个整数 $h$ 和 $w$ $(1\le h,w\le 10^3)$ 表示矩形纸张的长和宽。

## 输出格式

输出一行一个实数，表示正方形边长的最大可能值。

你的答案与标准答案的相对及绝对误差不应超过 $10^{-3}$。

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

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


title: [NWRRC2015] Black and White

description:
The jury has a great artistic idea -- to create a rectangular panel out of a huge pile of black and white squares of the same size. The panel should have exactly $b 4-connected$ areas made of black tiles, and $w 4-connected$ areas made of white tiles.

Remember, a $4-connected$ area of some color is a maximal set of the panel tiles such that:

any two tiles of the area share the same color;

for any two tiles of the area there is a tile sequence connecting them, such that any two consecutive tiles of the sequence share a common side.

In addition to the artistic idea, the jury has already developed a program that produces design of the panel. But since this problem is about art, any new solution is extremely important for the jury.

inputFormat: The only line of the input file contains two integers $b$ and $w$ -- number of black and white areas $(1 \le b , w \le 1000)$ .

outputFormat: The first line of the output file should contain the picture sizes $r$ and $c$ -- the number of rows and columns $(1 \le r , c \le 100 000)$ . This line should be followed by $r$ lines of $c$ symbols each. Each symbol should be either $‘@'$ (for black tile) or $‘. '$ (for white one). There should be no more than $100 000$ tiles in the panel.

translation:
给定正整数 $b,w$，请你构造出一个黑白矩阵，使得矩阵内恰有 $b$ 个黑色连通块和 $w$ 个白色连通块。

输出的第一行包含两个整数 $r,c$，表示你构造出的矩阵的行数和列数。接下来是一个 $r\times c$ 的矩阵，表示你构造出的黑白矩阵。其中 ```@``` 代表黑色，```.``` 代表白色。

数据范围：$1\le b,w\le 1000$

你的矩阵应满足：$1\le r,c\le 100000$ 且 $r\times c\le100000$


title: [NWRRC2015] Concatenation

description:
Famous programmer Gennady likes to create new words. One way to do it is to concatenate existing words. That means writing one word after another. For example, if he has words `cat` and `dog`, he would get a word `catdog`, that could mean something like the name of a creature with two heads: one cat head and one dog head.

Gennady is a bit bored of this way of creating new words, so he has invented another method. He takes a non-empty prefix of the first word, a non-empty suffix of the second word, and concatenates them. For example, if he has words `tree` and `heap`, he can get such words as `treap`, `tap`, or `theap`. Who knows what they could mean?

Gennady chooses two words and wants to know how many different words he can create using his new method. Of course, being a famous programmer, he has already calculated the answer. Can you do the same?

inputFormat: Two lines of the input file contain words chosen by Gennady. They have lengths between $1$ and $100 000$ characters and consist of lowercase English letters only.

outputFormat: Output one integer -- the number of different words Gennady can create out of words given in the input file.

translation:
### 题目描述

著名的程序员 Gennady 喜欢创造新单词。其中一种方法是连接现有单词。

举个例子：如果 Gennady 有 `cat` 和 `dog` 两个词，那么他会得到一个新词： `catdog`，这可能意味着带有两个头的生物的名字：一个猫头和一个狗头。

Gennady 觉得这种创建新单词的方式有点无聊，因此他发明了另一种方法：使用第一个单词的非空前缀，第二个单词的非空后缀，并将它们连接起来。例如，如果他有单词 `tree` 和 `heap` ，则可以得到诸如 `treap`，`tap` 或 `theap` 之类的单词。

Gennady 选择了两个单词，并想知道他可以使用新方法创建多少个不同的单词。当然，作为著名的程序员，他已经计算出了答案。他突然想考考你，那么你能编写一个程序把答案计算出来吗？

### 输入格式

两行，每行有一个 Gennady 选择的单词 $s_i$ （$1\leq |s_i| \leq 100000$，$s_i$ 仅由小写英文字母组成）。

### 输出格式

输出一个整数，这个整数表示 Gennady 可以从这两个给定的单词中创建不同单词的数量。


title: [NWRRC2015] Distribution in Metagonia

description:
There are one hundred noble families in the country of Metagonia, and each year some of these families receive several ritual cubes from the Seer of the One. The One has several rules about cube distribution: if a family receives at least one cube, every prime divisor of the number of cubes received should be either $2$ or $3$ , moreover if one family receives a $> 0$ cubes and another family in the same year receives $b > 0$ cubes then a should not be divisible by $b$ and vice versa.

You are the Seer of the One. You know in advance how many cubes would be available for distribution for the next $t$ years. You want to find any valid distribution of cubes for each of these years. Each year you have to distribute all cubes available for that year.

inputFormat: The first line of input file contains a single integer $t$ -- the number of years to come $(1 \le t \le 1000)$ . Each of the following $t$ lines contains a single integer $n_{i}$ -- the number of cubes to distribute in i-th year $(1 \le n_{i} \le 10^{18}).$

outputFormat: For each year $i$ output two lines. The first line should contain $m_{i}$ -- the number of families that would receive at least one cube in i-th year $(1 \le m_{i} \le 100)$ . The second line should contain $m_{i}$ integers -- the number of cubes received by each family. The sum of these numbers should be equal to $n_{i}.$

translation:
在一个叫做 镁铊铬铌氩$ (Metagonia)$ 的国度中，有$100$个贵族家庭。

每年，这些贵族家庭都要收到来自先知之首的若干个典礼用的小方块。先知有一些分配小方块的规则：

1. 如果某年有一个家庭收到了小方块，那么这个家庭所收到的小方块的个数的质因数只能是$2$和$3$。

2. 如果某年有一个家庭收到了$a>0$个小方块，同年另一个家庭收到了$b>0$个小方块，那么$a$不整除$b$，$b$也不整除$a$。

现在，你作为先知之首，你知道你接下来的$t$年中，你每年有多少个小方块。你现在想要找到任意一个可行的方案，以便在接下来$t$年中能够进行按规则分配。

--------

第一行，包含一个正整数$t(1≤t≤1000)$。

接下来有$t$行，每行有一个正整数$n_i(1≤n_i≤10^{18})$，表示在第$i$年中，你可以用于支配的小方块个数。

--------

对于每年输出两行。第一行应包含一个数$m_i$,表示能够收到小方块的家庭的数目。

第二行有$m_i$个整数，代表每个家庭应该收到的小方块的个数。这些整数之和应该等于$n_i$。

---------

时间限制：$2s$

空间限制：$256MB$

翻译提供：@Trexmao


title: [NWRRC2015] Easy Arithmetic

description: Eva is a third-grade elementary school student. She has just learned how to perform addition and subtraction of arbitrary-precision integers. Her homework is to evaluate some expressions. It is boring, so she decided to add a little trick to the homework. Eva wants to add some plus and minus signs to the expression to make its value as large as possible.

inputFormat:
The single line of the input file contains the original arithmetic expression. It contains only digits, plus $(‘+')$ and minus $(‘-')$ signs.

The original expression is correct, that is:

numbers have no leading zeroes;

there are no two consecutive signs;

the last character of the expression is a digit.

The length of the original expression does not exceed $1000$ characters.

outputFormat: Output a single line -- the original expression with some plus and minus signs added. Output expression must satisfy the same correctness constraints as the original one. Its value must be as large as possible.

translation:
## 题目翻译 ##

现向一个仅含有加减号和数字的表达式中添加一些加号或减号， 使得操作后的**合法**表达式的值最大， 并输出操作后的表达式。

当一个表达式合法时满足以下条件：

1.每一个数字**不含前导零**。

2.表达式里没有两个**连续的符号**。

3.表达式的最后一个字符是数字。

保证原始表达式是合法的， 且长度不大于 $1000$。


title: [NWRRC2015] Fygon

description:
Frederick is a young programmer. He participates in all programming contests he can find and always uses his favorite programming language Fygon. Unfortunately, he often receives Time Limit Exceeded outcome, even when his algorithm is asymptotically optimal. That's because the Fygon interpreter is very slow. Nevertheless, Frederick likes Fygon so much, that he uses non-asymptotical optimizations to fit the solution into time limit. To make it easier, he asks you to write a program, which will be able to estimate the exact number of operations that his Fygon program makes.

For simplicity, we will assume that Fygon has only two statements. The first statement is lag. It substitutes almost any other statement. The second statement is a for loop:

for in range $():$

This means that iterates over values from $0$ to $−1$ . In Fygon is a lowercase letter from a to $z$ , and is either already defined or a positive integer constant. The of the loop is indented by four spaces and contains at least one statement.

The program receives the input in the variable $n$ . This variable has special meaning and cannot be used as a loop variable.

Your task is to find the formula that calculates the number of performed lag operations by the given Fygon program, depending on the value of the variable $n$ .

inputFormat:
The input file contains the Fygon program. No two loops use the same variable as iterators. Each variable used inside a range is either $n$ or declared in some outer loop.

The program has at most $20$ statements and at most $6$ of them are loops. All integer constants are from $1$ to $9$ . Outpu

outputFormat:
Output the formula for the number of performed lag operations depending on $n$ . The length of the formula should be at most $100$ characters (excluding spaces). The formula should correspond to the following grammar:

$〈Expressio_n〉 ::= 〈Product〉 ( (‘+' | ‘-') 〈Product〉) ^{ \times }$

$〈Product〉 ::= 〈Value〉 (‘ \times '〈Value〉) ^{ \times }$

$〈Value〉 ::= ‘n' | 〈Number〉 | ‘-'〈Value〉 | ‘('〈Expressio_n〉‘)'$

$〈Number〉 ::= [‘0' \cdots ‘9'] ^{+} (‘/' [‘0' \cdots ‘9'] ^{+}) ^{?}$

translation:
# [NWRRC2015] Fygon 翻译

## 题目描述

弗雷德里克是一名年轻的程序员。他参加了所有能找到的编程比赛，并总是使用他最喜欢的编程语言 Fygon。不幸的是，他经常收到 "超过时间限制 "的结果，即使他的算法是渐近最优的。这是因为 Fygon 解释器非常慢。尽管如此，弗雷德里克还是非常喜欢 Fygon，所以他使用了非渐进优化的方法来使求解符合时间限制。为了方便起见，他要求你写一个程序，能够估算出他的 Fygon 程序所做的确切操作次数。

为了简单起见，我们假设 Fygon 只有两条语句。第一条语句是滞后的。它几乎可以替代任何其他语句。第二条语句是 for 循环：

for in range $():$

这意味着遍历从 $0$ 到 $-1$ 的值。 在 Fygon 中是从 $a$ 到 $z$ 的小写字母，并且要么是已经定义的，要么是正整数常数。循环语句缩进四个空格，至少包含一条语句。

程序接收变量 $n$ 的输入。该变量具有特殊含义，不能用作循环变量。您的任务是根据变量 $n$ 的值，找出计算 Fygon 程序执行滞后操作次数的公式。

## 输入格式

输入文件包含 Fygon 程序。没有两个循环使用相同的变量作为迭代器。范围内使用的每个变量要么是 $n$，要么是在某个外循环中声明的。

程序最多有 $20$ 语句，其中最多有 $6$ 是循环。所有整数常量从 $1$ 到 $9$ 不等。
## 输出格式

根据 $n$ 输出已执行滞后运算次数的公式。公式长度最多为 $100$ 字符（不包括空格）。公式应符合以下语法：

$〈表达式〉 ::= 〈产物〉 ( (‘+' | ‘-') 〈产物〉) ^{ \times }$

$〈产物〉 ::= 〈价值〉 (‘ \times '〈价值〉) ^{ \times }$

$〈价值〉 ::= ‘n' | 〈数〉 | ‘-'〈价值〉 | ‘('〈表达式〉‘)'$

$〈数〉 ::= [‘0' \cdots ‘9'] ^{+} (‘/' [‘0' \cdots ‘9'] ^{+}) ^{?}$

## 样例 #1

### 样例输入 #1

```
for i in range(n):
    for j in range(i):
        lag
for x in range(5):
    for y in range(n):
        for z in range(n):
            lag
    lag
```

### 样例输出 #1

```
1/2 * n * (n-1) + 5 * (n*n + 1)
```

## 提示

时间限制：2 秒，内存限制：256 MB。


title: [NWRRC2015] Graph

description:
The sequence $a_{1}, a_{2},$ . . . , $a_{n}$ is called a permutation, if it contains every integer from $1$ to $n$ .

The permutation of vertices $a_{1}, a_{2},$ . . . , $a_{n}$ is a topological sort of a directed graph, if for every directed edge from $u$ to $v$ , vertex $u$ comes before $v$ in this permutation.

The permutation $a_{1}, a_{2},$ . . . , $a_{n}$ is lexicographically smaller than the permutation $b_{1}, b_{2},$ . . . , $b_{n},$ if there exists $m$ such that $a_{i} = b_{i}$ for every $1 \le i < m$ and $a_{m} < b_{m}.$

Given a directed acyclic graph, add at most $k$ directed edges to it in such a way, that the resulting graph still has no cycles and the lexicographically minimal topological sort of the graph is maximum possible.

inputFormat:
The first line of the input file contains three integers $n , m$ and $k$ -- the number of vertices and directed edges in the original graph, and the number of directed edges, that you are allowed to add $(1 \le n \le 100 000$ ; $0 \le m , k \le 100 000)$ .

Each of the following $m$ lines contains two integers $u_{i}, v_{i},$ describing directed edge from $u_{i}$ to $v_{i} (1 \le u_{i}, v_{i} \le n)$ .

The graph has no cycles.

outputFormat: The first line of the output file should contain $n$ integers -- the lexicographically minimal topological sort of the modified graph. The second line should contain a single integer $x (0 \le x \le k)$ -- the number of directed edges to add. The following $x$ lines of the output should contain description of added directed edges in the same format as in the input file.

translation:
给定一张 $n$ 点 $m$ 条边的有向无环图，你可以至多添加 $k$ 条有向边，使得这仍然是一个有向无环图，使得字典序最小的拓扑序的字典序尽量大。

输出这个拓扑序以及方案。

$n,m,k\le 10^5$


title: [NWRRC2015] Hash Code Hacker

description:
According to Java standard library documentation, the hash code of String is computed as

$s[0] \times 31 ^ {n -1} + s[1] \times 31 ^ {n -2} + \cdots + s[n -1]$

Here $s[i]$ is the i-th character of the string, $n$ is the length of the string, and $^$ indicates exponentiation. Computation uses signed $32-bit$ integers in two's complement form.

Heather is going to hack the servers of Not Entirely Evil Recording Company $(NEERC).$ To perform an attack she needs $k$ distinct query strings that have equal hash codes. Unfortunately, NEERC servers accept query string containing lower- and uppercase English letters only.

Heather hired you to write a program that generates such query strings for her.

inputFormat: The single line of the input file contains integer $k$ -- the number of required query strings to generate $(2 \le k \le 1000)$ .

outputFormat: Output $k$ lines. Each line should contain a single query string. Each query string should be non-empty and its length should not exceed $1000$ characters. Query string should contain only lower- and uppercase English letters. All query strings should be distinct and should have equal hash codes.

translation:
根据$Java$的标准库文件，字符串的哈希代码是这么计算的：

$$s[0]×31 ^{(n−1)}+s[1]×31^{(n−2)}+⋯+s[n−1]$$

在这里，s[i]指的是字符串中的第i位，n是字符串的长度。

这个计算过程用的是有符号的$32$位整数的二进制补码形式。

有一个人叫作 阖锕仄 $(Heather)$。他想要$hack$掉“不全是恶魔录音公司”$(NEERC)$。为了进行

一次攻击，阖锕仄需要$k$个有相同哈希代码的不同的询问字符串。不幸的是，$NEERC$的服务器

只接受只包含大小写字母的字符串。

阖锕仄请你帮忙写一个程序，以生成他需要的询问字符串。

-------

输入一个正整数$k$,代表需要的字符串的数量。

-------

输出有$k$行，每行的询问字符串都不应该为空，并且每行的字符串的长度应该小于等于1000个字符。

询问字符串的具体要求请看上文。

-------

时间限制：$2s$

空间限制：$256MB$

翻译提供：@Trexmao


title: [NWRRC2015] Insider’s Information

description:
Ian works for a rating agency that publishes ratings of the best universities. Irene is a journalist who plans to write a scandalous article about the upcoming rating.

Using various social engineering techniques (let's not get into more details), Irene received some insider's information from Ian.

Specifically, Irene received several triples $(a_{i}, b_{i}, c_{i}),$ meaning that in the upcoming rating, university $b_{i}$ stands between universities $a_{i}$ and $c_{i}.$ That is, either $a_{i}$ comes before $b_{i}$ which comes before $c_{i},$ or the opposite. All triples told by Ian are consistent -- let's say that actual rating satisfies them all.

To start working on the first draft of the future article, Irene needs to see at least some approximation to the actual rating. She asked you to find a proposal of a rating in which at least half of the triples known by Irene are satisfied.

inputFormat:
The first line contains integers $n$ and $m$ , the number of rated universities, and the number of triples given to Irene by Ian $(3 \le n \le 100 000$ ; $1 \le m \le 100 000)$ .

Each of the next $m$ lines contains three distinct integers $a_{i}, b_{i}, c_{i}$ -- the universities making a triple $(1 \le a_{i}, b_{i}, c_{i} \le n)$ .

outputFormat: Output the proposal of a rating from the first university to the last one. The proposal rating should satisfy at least $m/2$ triples. If there are many such proposals, output any one of them.

translation:
## 题意

对于 $[1, n]$ 的排列，给 $m$ 个限制，第 $i$ 个限制描述 $b_i$ 出现在 $a_i$，$c_i$ 之间。保证存在一个排列满足所有限制。

构造一个 $n$ 的排列至少满足 $\lceil \frac m2 \rceil$ 个限制。


title: [NWRRC2015] Journey to the “The World’s Start”

description:
Jerry Prince is the fourth grade student and he goes to New-Lodnon to visit the most popular amusement park `The World's Start`.

An airport he arrives at is next to the first stop of the metro line. This line has $n$ stops and `The World's Start` is on the last of them. The metro of New-Lodnon is pretty fast so you may assume that you can get from a stop to the next one in just one minute.

Jerry needs a travel card to use the metro. Each travel card has a range $r$ and a price $p$ . With a travel card of range $r$ Jerry may travel no more than $r$ stops at once. Therefore, if Jerry enters metro at the stop $i$ he should exit on one of the stops from $i − r$ to $i + r$ inclusive. It takes $d_{i}$ minutes to exit and reenter metro at i-th stop. There is no time required to enter the first stop or exit the last one.

Jerry is not very rich but he has some spare time, so he decided to buy the cheapest travel card that will allow him to travel from the first metro stop to the last one in no more than $t$ minutes.

inputFormat:
The first line of the input file contains two integers $n$ and $t$ -- the number of stops and the maximum possible time $(2 \le n \le 50 000$ ; $n - 1 \le t \le 10^{9}).$

The second line contains $n - 1$ integers $p_{r}$ -- the prices of travel cards with range $r = 1$ . . . $n − 1 (1 \le p_{r} \le 100 000)$

The third line contains $n - 2$ integers $d_{i}$ -- the number of minutes required to reenter metro at stop $i = 2$ . . . $n - 1 (1 \le d_{i} \le 10^{5}).$

outputFormat: Output a single integer $p$ -- the lowest possible price of one travel card that allows Jerry to travel from the first to the last stop in no more than $t$ minutes.

translation:
杰瑞在一条地铁线路上，这条线有$n$个站，世界的起点在最后一个，地铁很快，你可以在一分钟内从一个站点到达下一个站点。

杰瑞需要一张旅行卡才能乘地铁。每张旅行卡都有一个范围$r$和价格$p$。使用范围为$r$的旅行卡，他一次就只能最多旅行$r$站。因此，如果他在第二站进入地铁，他应该在$i−r$到$i+r$的其中一站下车。它需要$d[i]$在第一站下车或者重新进入地铁，不需要时间进入第一站或离开最后一站。

杰瑞不是很富有，但他有一些空闲时间，所以他决定买一张最便宜的旅行卡，这样他就可以在不超过$t$分钟的时间内从地铁的第一站坐到到最后一站。


title: [NWRRC2015] Kingdom Trip

description:
Once upon a time, there was a kingdom ruled by a wise king. After forty three years of his reign, by means of successful military actions and skillful diplomacy, the kingdom became an infinite flat two-dimensional surface. This form of the kingdom greatly simplified travelling, as there were no borders.

A big holiday was planned in the kingdom. There were $n$ locations for people to gather. As the king wanted to have a closer look at his people, he ordered to make a trip through these locations. He wanted to give a speech in each of these locations. Initially his trip was designed as a polygonal chain $p$ : $p_{1} \to p_{2} \to $ . . . $ \to p_{n}.$

Not only the king was wise, but he was old, too. Therefore, his assistants came up with an idea to skip some locations, to make the king to give as few speeches as possible. The new plan of the trip has to be a polygonal chain consisting of some subsequence of $p$ : starting at $p_{1}$ and ending at $p_{n},$ formally, $p_{i_{1}} \to p_{i_{2}} \to · · · \to p_{i_{m}},$ where $1 = i_{1} < i_{2} < · · · < i_{m} = n$ . Assistants know that the king wouldn't allow to skip location $j$ , if the distance from $p_{j}$ to segment $p_{i_{k}} \to p_{i_{k+1}}$ exceeds $d$ , for such $k$ , that $i_{k} < j < i_{k+1}.$

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

Original route

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

New route

Help the assistants to find the new route that contains the minimum possible number of locations.

inputFormat:
The first line of the input file contains two integers $n$ and $d$ -- the number of locations in the initial plan of the trip and the maximum allowed distance to skipped locations $(2 \le n \le 2000$ ; $1 \le d \le 10^{6}).$

The following $n$ lines describe the trip. The i-th of these lines contains two integers $x_{i}$ and $y_{i}$ -- coordinates of point $p_{i}.$ The absolute value of coordinates does not exceed $10^{6}.$ No two points coincide.

outputFormat: Output the minimum number of locations the king will visit. It is guaranteed that the answer is the same for $d ± 10^{−4}.$

translation:
## 题目描述
很久以前，一位明智的国王统治着一个王国。在他长达43年的统治后，通过成功的军事行动和熟练的外交技巧，这个王国变成了一个无限的平面二维曲面。因为没有边界，这种方式大大地简化了王国的出行。

王国内准备举行一个盛大的节日。人们能聚集在$n$个地点。因为国王想要近一点地看到他的子民，所以他下令去这些地点旅行。他想在每个地点演讲。起初他的旅行被计划成了一串多边形链$P$:从$P_1$到$P_n$。

国王虽然很明智，但他也已经老了。因此，他的助手想出了一个方法来跳过部分地点，来确保国王演讲的次数能尽可能地少。旅程的新计划需要是一串由某个子序列所构成的多边形链$P$:从$P_1$到$P_n$，正规的表示为：从$P_{i_1}$到$P_{i_m}$，且$1=i_1<i_2<...<i_m=n$。国王的助手知道国王不会允许跳过地点$j$，如果$P_j$与$P_{i_k}$到$P_{i_{k+1}}$这一段的距离超过了$d$，对于每个$k$，$i_k<j<i_{k+1}$。

## 输入
第一行，包含两个整数$n$和$d$，分别表示最初的路线的地点数和跳过地点被允许的距离的最大值（$2≤n≤2000$;$1 \le d \le 10^6$)

接下来$n$行，第$i$行包含两个整数$x_1$和$y_1$，表示点$P_i$的坐标。坐标的绝对值不超过$10^6$。不会出现两个点重合的情况。

## 输出

输出国王经过的地点数量的最小值，答案保证在$d \pm 10^{-4}$内；

------------

时间限制：2秒，内存限制：256MB


title: [NWRRC2015] Lucky Chances

description:
Lucky Chances is a lottery game. Each lottery ticket has a play field and a scratch area. The play field is a rectangular $r \times c$ field filled with numbers. The scratch area hides row and column numbers that specify the bet cell.

There are four possible winning directions: up, down, left and right. You win a direction if all numbers in this direction from the bet cell are strictly less than a number in the bet cell. And if the bet cell is on the edge of the grid, you win the corresponding direction automatically!

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

Unscratched ticket

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

Scratched ticket $1$

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

Scratched ticket $2$

Larry wants to choose the ticket that has maximum total number of winning directions for all possible bet cells. Write a program that determines this number for the given grid.

inputFormat:
The first line of the input file contains two integers $r$ and $c$ -- the number of rows and columns in the grid $(1 \le r , c \le 100)$ .

The following $r$ lines contain $c$ integers each -- the numbers printed on the grid. Each number is positive and does not exceed $1000$ .

outputFormat: Output a single integer $w$ -- the total number of winning directions for the given grid.

translation:
有一个名叫 Lucky chances 的游戏，游戏一开始给出一个 $r\times c$ 的矩阵，你可以选定矩阵中任意一个元素以及上、下、左、右四个方向中的任意一个方向进行游戏。如果这个方向上的任意一个元素都**严格小于**所选的元素，那么你就赢了。

试求出所有元素的能够使得你赢得游戏的方向的总和。

Translated by Eason_AC
2020.11.15


title: [NWRRC2014] Alarm Clock

description:
Alice likes her digital alarm clock. She sets them up every evening. Last night Alice had a dream about her clock. Unfortunately, the only thing she is able to remember is the number of highlighted segments of the clock. Alice wonders what time was set on the clock in her dream.

Alice's clock have four digits: two for hours and two for minutes. For example, the clock below shows $9:30$ (note the leading zero).

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

The clock uses following digit representation.

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

inputFormat: The only line of the input file contains single integer $n$ — the number of highlighted segments of the clock in Alice's dream $(0 \le n \le 30)$ .

outputFormat: Output five characters in $\text{hh:mm}$ format — the time shown on the clock in Alice's dream. The time must be correct: $0 \le \text{hh} < 24$ and $0 \le \text{mm} < 60$ . If there are many possible correct times, output any of them. If there is none, output `Impossible`.

translation:
Alice梦见了一个时间，但她只记得了这个时间在电子钟上显现出来的**段数**，现在给出这个段数，让你反推Alice梦见的时间（若有多个答案，输出任意一个均可）
**段数**：想必大家都听说过用火柴拼数字的游戏，比如1要用两个火柴，2要用5根火柴，8要用7根火柴等等（如题目图片所示），这里的**段数**指的就是一个时间的每一个数字，需要火柴数量的和（比如09：30，就要6+6+5+6=23个火柴）。
**时间**：本题输出的时间仅有小时和分钟，其中小时在0到23之间，分钟在0到59之间

输入一个整数n，n在0到30以内，代表Alice梦见的**段数**
输出一个字符串，如果有合法的时间满足输入的段数，则输出这个时间（有多个输出任意一个均可），否则输出`Impossible`

注意时间的前导零

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

spj provider: @[rzh123](user/237530)


title: [NWRRC2014] Buffcraft

description:
Brenda enjoys a new role-playing game Buffcraft. Shields, swords, books and other carry-on items do not affects character stats in Buffcraft. The only way to increase the stats of your character is to buff her.

There are two types of buffs in Buffcraft. Direct buffs increase a base value of the stat, while percentage buffs increase stats by the fraction of the base value. To be precise, if unbuffed base value of your character stat is $b$ , you have buffed her using $n$ direct buffs of strength $d_1 , d_2 , \cdots d_n$ and $m$ percentage buffs of strength $p_{1}, p_{2}, \cdots , p_{m},$ the resulting stat will be equal to $(b + d_{1} + d_{2} + · · · + d_{n})(100 + p_{1} + p_{2} + · · · + p_{m})/100$ . Note that the resulting stat may be fractional.

Unfortunately, your character has only $k$ buff slots and if you apply more than $k$ buffs on her, only the last $k$ buffs remains active. Thus, there is no reason to apply more than $k$ buffs simultaneously. You cannot apply the same buff more than once.

Brenda is going to send his character to raid and wants to buff her health to maximal possible value. She has some direct and some percentage buffs at her disposal and needs your help to select the set of buffs that leads to maximal possible total health.

inputFormat:
The first line of the input file contains four integers $b , k , c_{d}$ and $c_{p}$ — the base health of the character, the number of buff slots, the number of available directs buffs, and the number of available percentage buffs.

The following line contains $c_{d}$ integers $d_{i}$ — strengths of direct buffs.

The last line of the input file contains $c_{p}$ integer numbers $p_{i}$ — strengths of percentage buffs.

All numbers in the input file are greater than or equal to zero, and less than or equal to fifty thousand.

outputFormat:
The first line of the output file must contain two integers $n$ and $m$ — the number of direct and percentage buffs to use $(0 \le n \le c_{d}; 0 \le m \le c_{p}; 0 \le n + m \le k)$ .

The following line must contain $n$ different numbers — indices of direct buffs to apply (buffs are numbered from one).

The last line of the output must contain $m$ different numbers — indices of percentage buffs to apply (also numbered from one).

The resulting total health after application of all $n + m$ buffs must be maximal possible.

translation:
## 题目描述
Brenda喜欢一款新的游戏Buffcraft。没有任何物品可以影响Buffcraft中的角色属性。增加你角色属性的唯一方法就是给予它buff。

Buffcraft中有两种类型的buff。
1.直接增加buff的值;
2.百分比增加buff的值;
如果你的角色buff初始值是$b$，那么你使用$n$个增益分别为$d_1,d_2,\cdots,d_n$的第一种buff和$m$个增益分别为$p_{1},p_{2}\cdots,p_{m}$的第二种buff，得到的结果将等于$(b+d_{1}+d_{2}+··+d_{n})(100+p_{1}+p_{2}-··+p_{m})/100$。请注意，这个结果可能不是整数。

不幸的是，你的角色只有$k$个buff槽，如果你在她身上应用了$k$个以上的buff，那么只有最后的$k$个buff有效。因此，你不能同时拥有$k$个以上buff。当然，一个buff不能被多次使用。

Brenda将派她的角色去战斗，并希望将角色的buff值提升到最大。有一些第一种buff和一些第二种buff可供她使用。她需要你的帮助来选择一种buff的搭配方式，以获得最大可能的总buff值。

## 输入格式
第一行包含四个整数$b,k,n,m$；分别代表角色的基础buff值、buff槽数、第一种buff的数量与第二种buff的数量。
第二行包含$n$个整数$d_{i}$，代表每个第一种buff的增益量。
第三行包含$m$个整数$p_{i}$，代表每个第二种buff的增益量。

## 输出格式
第一行是两个整数$x,y$代表用了多少第一种buff和用了多少第二种buff。$(0 \le x \le n; 0 \le y \le m; 0 \le x + y \le k)$ .

第二行是$x$个数字-要应用的每一个第一种buff的索引。
第二行是$y$个数字-要应用的每一个第二种buff的索引。
你的方案要让所有buff应用后产生的总buff值尽可能最大。

## 输入输出样例

### 样例输入#1
```
70 3 2 2
40 30
50 40
```
### 样例输出#1
```
2 1
2 1
1
```
### 样例输入#2
```
1 2 3 4
6 6 5
8 10 7 9
```
### 样例输出#2
```
2 0
1 2
```
## 说明/提示
$0 \le b,k,n,m,d_{i},p_{i} \le 50000$
数组的索引从1开始
时间限制:2s;空间限制:256MB。


title: [NWRRC2014] Combinator Expression

description:
Combinatory logic may be thought as one of computational models allowing to express any computable function as a composition of functions from a small finite basis. In this problem we consider a restricted variant of BCKW basis, BCKI.

Combinator expression in BCKI basis is a string, corresponding to the following grammar:

```plain
⟨Expression⟩ ::= ⟨Expression⟩ ⟨Term⟩ | ⟨Term⟩
⟨Term⟩ ::= ‘(’⟨Expression⟩‘)’ | ‘B’ | ‘C’ | ‘K’ | ‘I’
```

As we can see from the grammar, the expression is a tree of applications where leafs are combinators $B, C, K$ and $I$. The application is left-associative. For example $BIC$ is equivalent to $(BI)C,$ but not to $B(IC)$.

For the sake of the explanation we will use lowercase English letters $(a \cdots z)$ to represent sub-expressions. These lowercase letters will not appear in real data. For example, $BIC$ can be represented by $BxC$ (that is, $B\underbrace { I }_{ x }C)$, $x(\underbrace {BIC}_{ x })$, $xy(\underbrace {BI}_{ x } \underbrace { C }_{ y })$, $Bxy (B\underbrace { I }_{ x }\underbrace { C }_{ y })$, but not by $Bx$.

We say that in expression $pq$ we apply $p$ to $q$. We can employ our intuition by saying that $p$ is a function and $q$ is its parameter. However, the evaluation process is quite different from traditional computation — instead of passing values over fixed expression tree, we evaluate by altering that tree so that the result is also some combinator expression.

To evaluate an expression, we need to select some sub-expression, corresponding to one of the patterns specified in the table below — that is, there should exist such $x$ (and maybe $y$ and $z$) that the pattern from the table becomes equal to the sub-expression. Then we need to replace the sub-expression with the reduction result from the table.

| Pattern | Reduction result |                   Description                   |
| :-----: | :--------------: | :---------------------------------------------: |
| $Bxyz$  |     $x(yz)$      | Composition function (Zusammensetzungsfunktion) |
| $Cxyz$  |     $(xz)y$      |    Exchange function (Vertauschungsfunktion)    |
|  $Kxy$  |       $x$        |      Constant function (Konstanzfunktion)       |
|  $Ix$   |       $x$        |     Identity function (Identitätsfunktion)      |

After the replacement took place we must repeat the process, until there remains no suitable subexpressions. This final expression is normal form of the original one. For example, in expression $CIC(CB)I$ we can make the following letter assignment

$$\underbrace { C }_{ C }\underbrace { I }_{ x }\underbrace { C }_{ y }\underbrace {(CB)}_{ z }I$$

and see that $CIC(CB)I ≡ (((CI)C)(CB))I ≡ (((Cx)y)z)I$ contains $C$ combinator pattern and thus reduces to $((xz)y)I ≡ I(CB)CI:$

$$(\underbrace { C }_{ C }\underbrace { I }_{ x }\underbrace { C }_{ y }\underbrace { (CB) }_{ Z })I \rightarrow (\underbrace { I }_{ x } \underbrace {(CB)}_{ z }\underbrace { C }_{ y })I$$

One more example: $B((CK)I)IC$ expression. Let us first reduce combinator $B:$

$$(\underbrace { B }_{ B }\underbrace { ((CK)I) }_{ x }\underbrace { I }_{ y }\underbrace { C }_{ z } \rightarrow \underbrace { ((CK)I) }_{ x } (\underbrace { I }_{ y }\underbrace { C }_{ z })$$

Now, let's reduce the last $I:$

$$((CK)I)(\underbrace { I }_{ I } \underbrace { C }_{ x }) \rightarrow ((CK)I)C$$

And now we finish evaluation with two more reductions:

$$((\underbrace { C }_{ C }\underbrace { K }_{ x }) \underbrace { I }_{ y }) \underbrace { C }_{ z } \rightarrow (\underbrace { K }_{ K }\underbrace { C }_{ x }) \underbrace { I }_{ y } \rightarrow C$$

It is possible to show that the normal form remains the same irrespectable to the order of evaluation. For example, the following evaluation order:

$$C(K(II)(\underbrace { I }_{ I }\underbrace { C }_{ x })) \rightarrow C(K(\underbrace { I }_{ I }\underbrace {  I}_{ x })(C)) \rightarrow C((\underbrace { K }_{ K }\underbrace { I }_{ x }) \underbrace { C }_{ y }) \rightarrow CI$$

leads to the same result as

$$C(K(\underbrace {I}_{ I }\underbrace { I }_{ x })(IC)) \rightarrow C((\underbrace { K }_{ K }\underbrace { I }_{ x })\underbrace { (IC)}_{ y }) \rightarrow CI$$

However, as you see, the number of reductions is different: $3$ in the first case and $2$ in the second. This poses an interesting problem -- to find an evaluation order with the minimal number of reductions for a given formula.

Your task is to write a program which finds the minimal number of reductions required for a given combinator expression to be evaluated to its normal form.

inputFormat: The only line of the input file contains a combinator expression corresponding to the grammar above. The length of the expression does not exceed $30 000$ . The expression contains no whitespaces or symbols not specified in the grammar.

outputFormat: Output a single integer — the minimal number of reductions required for the given formula to evaluate it to normal form.

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


title: [NWRRC2014] Digits

description:
Little Petya likes integers. Recently he has learned about different properties of sums of number's digits. For example, if the sum of number's digits is divisible by $9$ , then the number itself is divisible by $9$ as well.

Now little Petya is interested in numbers with equal sum of digits. He asks his older brother Dima to find $n$ positive integers with equal sum of digits and minimal possible total sum. Dima has other important things to do, so he asked you to write a program that solves this problem for him.

inputFormat: Input file contains a single integer $n (1 \le n \le 5000)$ .

outputFormat: Output the minimal possible sum of $n$ positive integers, that all have same sum of digits.

translation:
输入一个整数n，要求找到n个不同的正整数，使得这n个正整数**数位和**一样且总和最小，输出这个总和
**数位和**：一个数每一位的值的和，比如123的数位和为1+2+3=6

样例一解释：选择了1和10两个数
样例二解释：选择了2，11和20这三个数


title: [NWRRC2014] Expression

description:
In computing, regular expressions is a powerful tool for text search and string matching. In this problem a simplified version of regular expressions is used:

- An empty string ` ` is a regular expression, only the empty string matches it.

- A single lowercase letter `c` is a regular expression, a string consisting of a single letter $c$ matches it.

- A dot `.` is a regular expression, a string consisting of any single letter matches it.

- Alternation: if $α$ and $β$ are regular expressions then `(α|β)` is a regular expression, a string $s$ matches it only if $s$ matches $α$ or $s$ matches $β$.

- Concatenation: if $α$ and $β$ are regular expressions then `(αβ)` is a regular expression, a string $s$ matches it only if $s =$ `xy`, $x$ matches $α$ and $y$ matches $β$.

- Kleene star: if $α$ is regular expression then `(α∗)` is a regular expression, a string $s$ matches it only if $s$ is empty or $s =$ `xy`, $x$ is nonempty and matches $α$ and $y$ matches $(α∗).$ In other words, $s$ consists of zero or more strings, each of them matches $α.$

Parentheses can be omitted, in this problem Kleene star has the highest priority, concatenation has medium priority and alternation has lowest priority. Thus `abc*|de` means `(ab(c*))|(de)`.

For example, string `abcabcab` matches `a(bc|a)*ab`, but string `abcbab` does not.

Your task is to find the shortest string that matches the given regular expression $E$ and contains the given substring $S$ .

inputFormat:
The first line of the input file contains the regular expression $E$ . The second line of the input file contains the substring $S (1 \le |E| , |S| \le 10 000)$ .

String $S$ consists of lowercase English letters. Expression $E$ consists of lowercase English letters and special characters: dots (`.`), parentheses (`(`) and (`)`), pipes (`|`), and asterisks (`*`).

outputFormat:
Output the shortest possible string $T$ that both matches $E$ and contains $S$ as substring. If there are no such strings, output `NO`.

The string $T$ should contain only lowercase English letters.

translation:
在计算机中，正则表达式是文本搜索和字符串匹配的强力工具。这道题将使用简化后的正则表达式：

+ 一个空字符串()是一个正则表达式，且只有空字符串匹配它。

+ 一个小写字母(c)是一个正则表达式，只有仅包含一个字母 $c$ 的字符串匹配它。

+ 点(.)是一个正则运算符，任何仅包含一个字母的字符串都匹配它。

+ 或运算：若 $\alpha$ 和 $\beta$ 是正则表达式，则 ( $\alpha$ | $\beta$ ) 是正则表达式；当且仅当字符串 $s$ 匹配 $\alpha$ 或 匹配 $\beta$ 时，$s$ 匹配 ( $\alpha$ | $\beta$ )。

+ 与运算：若 $\alpha$ 和 $\beta$ 是正则表达式，则 ( $\alpha\beta$ ) 是正则表达式；当且仅当字符串 $s$ 可以分为两个子串 $x$ 和 $y$ ，且 $x$ 匹配 $\alpha$ ，$y$ 匹配 $\beta$ 时，$s$ 匹配 ( $\alpha\beta$ )。

+ 星号运算：若 $\alpha$ 是正则表达式，则 ( $\operatorname{\alpha_*}$ ) 是正则表达式；当且仅当字符串 $s$ 为空或 $s$ 可以被分为若干个匹配 $\alpha$ 的子串时，$s$ 匹配 ( $\operatorname{\alpha_*}$ )。

在本题中，括号可以被省略；运算符的优先级从高到低依次为：星号运算、与运算，或运算。所以 ( $abc_*$ | $de$ ) 即 ( $ab$ ( $c_*$ )) | ( $de$ ) 。

举个例子，字符串 $abcabcab$ 匹配 ( $a$ ( $bc$ | $a$ )$_*ab$ )，而字符串 $abcbab$ 并不匹配它。

现给定正则表达式 $E$ 和字符串 $S$ ，要求找出最短的匹配 $E$ 的字符串 $T$ ，且 $T$ 必须包含 $S$ 。

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


title: [NWRRC2014] Fragmentation

description:
Felix is working on a startup project in his garage. He has already found a great name for his project: SuperFastZilla. By now he is not sure what SuperFastZilla should do, but he is pretty sure it should do it fast, super fast.

Once he noticed that SuperFastZilla is working too slow, inspite of the fast algorithms used in it. Felix thinks that the problem may be caused by storage fragmentation.

The storage used by SuperFastZilla consists of $n$ blocks of memory. SuperFastZilla performs some operations on this storage. Each block is used in one operation only, the i-th block is used in the $a_{i}$-th operation.

Felix wants to sort these blocks by the index of the operation they are used. To make it faster, Felix wants to split the storage into minimal number of segments of consecutive blocks, and then rearrange these segments to get the sorted array of blocks. After this rearrangement the order of block's indices of operations must be non-decreasing.

Help Felix to find the way to split the storage that minimizes the number of segments.

For example, if $a = [2 , 3 , 1 , 1 , 2 , 2 , 1],$ it can be split into three parts: $[2 , 3], [1 , 1 , 2 , 2]$ and $[1].$ These parts can be rearranged to make the sorted array: $[1], [1 , 1 , 2 , 2], [2 , 3].$

inputFormat: The first line of input file contains an integer $n (1 \le n \le 10^{5}).$ The next line contains $n$ integers $a_{i} (1 \le a_{i} \le 10^{5}).$

outputFormat:
The first line of the output file must contain an integer number $m$ — the minimal number of segments.

The next line must contains $m$ integers, the lengths of the segments, from left to right.

translation:
给定一个长度为 $n$ 的数组，你需要把它分成尽量少的段，使得你可以排列这些段令整个数组有序。

$n,a_i \le 10^5$


title: [NWRRC2014] Grave

description:
Gerard develops a Halloween computer game. The game is played on a rectangular graveyard with a rectangular chapel in it. During the game, the player places new rectangular graves on the graveyard. The grave should completely fit inside graveyard territory and should not overlap with the chapel. The grave may touch borders of the graveyard or the chapel.

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

Gerard asked you to write a program that determines whether it is possible to place a new grave of given size or there is no enough space for it.

inputFormat:
The first line of the input file contains two pairs of integers: $x_{1}, y_{1}, x_{2}, y_{2} (−10^{9} \le x_{1} < x_{2} \le 10^{9}; −10^{9} \le y_{1} < y_{2} \le 10^{9})$ — coordinates of bottom left and top right corners of the graveyard. The second line also contains two pairs of integers $x_{3}, y_{3}, x_{4}, y_{4} (x_{1} < x_{3} < x_{4} < x_{2}; y_{1} < y_{3} < y_{4} < y_{2})$ — coordinates of bottom left and top right corners of the chapel.

The third line contains two integers $w , h$ — width and height of the new grave $(1 \le w , h \le 10^{9}).$ Side with length $w$ should be placed along OX axis, side with length $h$ — along OY axis.

outputFormat: The only line of the output file should contain single word: `Yes`, if it is possible to place the new grave, or `No`, if there is not enough space for it.

translation:
在一块长方形的墓地上，有一个长方形的教堂，现在给出一个长宽已知的墓碑，墓碑不能与教堂重叠，询问这块墓地上能否放下这块墓碑。

输入第一行两对坐标，代表墓地左下角和右上角的坐标（先 $x$ 轴再 $y$ 轴）；
第二行也是两对坐标，代表教堂左下角和右上角的坐标（先 $x$ 轴再 $y$ 轴）（保证教堂完全在墓地内部且边缘不重叠）；
第三行两个整数 $w$ 和 $h$，代表墓碑的长与宽，要求长度为 $w$ 的一侧必须对应 $x$ 轴，长度为 $h$ 的一侧必须对应 $y$ 轴。

输出一行一个字符串，如果放得下，输出 `Yes`，否则输出 `No`。