---

```
n, k = map(int, input().split())
p = list(map(int, input().split()))

L = 0
R = n
for i in range(n - 1):
    a, b = p[i], p[i + 1]
    if a > b:
        a, b = b, a
    if a > L:
        L = a
    if b - 1 < R:
        R = b - 1

if L > R:
    print(-1)
else:
    print(' '.join(str(x if x <= L else x + k) for x in p))
```

1574
личный сертификат


```
import random
from collections import Counter

n, K = map(int, input().split())
P = [list(map(int, input().split())) for _ in range(K)]

if K == 1:
    print("YES")
    raise SystemExit

if len(set(map(tuple, P))) < K:
    print("NO")
    raise SystemExit

lo_n = min(n, 8)
hi_n = n - lo_n
LO = []
HI = []
for p in P:
    lo = [0] * (1 << lo_n)
    for s in range(1, 1 << lo_n):
        b = (s & -s).bit_length() - 1
        lo[s] = lo[s & (s - 1)] | (1 << (p[b] - 1))
    hi = [0] * (1 << hi_n)
    for s in range(1, 1 << hi_n):
        b = (s & -s).bit_length() - 1
        hi[s] = hi[s & (s - 1)] | (1 << (p[lo_n + b] - 1))
    LO.append(lo)
    HI.append(hi)

ok = [False] * K
mlo = (1 << lo_n) - 1
total = 1 << n
rng = range(K)
for _ in range(400):
    S = random.randrange(total)
    a = S & mlo
    b = S >> lo_n
    vals = [LO[j][a] | HI[j][b] for j in rng]
    cnt = Counter(vals)
    for j in rng:
        if cnt[vals[j]] == 1:
            ok[j] = True
    if all(ok):
        break

inv = []
for p in P:
    q = [0] * n
    for x in range(n):
        q[p[x] - 1] = x
    inv.append(q)

full = (1 << total) - 1
cache = {}

for i in rng:
    if ok[i]:
        continue
    pi = P[i]
    U = 0
    for j in rng:
        if j == i:
            continue
        ij = inv[j]
        sigma = [ij[pi[x] - 1] for x in range(n)]
        seen = 0
        masks = []
        for x in range(n):
            if seen >> x & 1:
                continue
            m = 0
            y = x
            while not (m >> y & 1):
                m |= 1 << y
                y = sigma[y]
            seen |= m
            masks.append(m)
        masks.sort()
        key = tuple(masks)
        L = cache.get(key)
        if L is None:
            L = 1
            for m in masks:
                L |= L << m
            cache[key] = L
        U |= L
        if U == full:
            break
    if U == full:
        print("NO")
        raise SystemExit

print("YES")
```

1573
Последний прилив

```
def grundy(block):
    if '1' not in block:
        return len(block) % 2

    left = len(block) - len(block.lstrip('2'))
    right = len(block) - len(block.rstrip('2'))
    ones = len(block) - left - right

    if left == 0 or right == 0:
        return ones % 2 ^ (3 if (left + right) % 2 else 0)

    if min(left, right) == 1:
        return 2 if (left + right) % 2 else 0

    return (left + right) % 2


t = int(input())

for _ in range(t):
    n = int(input())
    s = input().strip()

    result = 0

    for block in s.split('0'):
        result ^= grundy(block)

    print("Mira" if result else "Lev")

```

1573
Последний прилив

```
def grundy(block):
    if '1' not in block:
        return len(block) % 2

    left = len(block) - len(block.lstrip('2'))
    right = len(block) - len(block.rstrip('2'))
    ones = len(block) - left - right

    if left == 0 or right == 0:
        return ones % 2 ^ (3 if (left + right) % 2 else 0)

    if min(left, right) == 1:
        return 2 if (left + right) % 2 else 0

    return (left + right) % 2


t = int(input())

for _ in range(t):
    n = int(input())
    s = input().strip()

    result = 0

    for block in s.split('0'):
        result ^= grundy(block)

    print("Mira" if result else "Lev")

```
1582
Место у фонтана

```
n, K, C = map(int, input().split())
a = list(map(int, input().split()))
M = 1 << 18
NEG = -(1 << 200)


def evaluate(d, num):
    mul = d * M
    pen = num * M + 1
    F = [0] * (C + 1)
    app = F.append
    cur = NEG
    f = 0
    i = 0
    for x in a:
        s = F[i] - pen
        if s > cur:
            cur = s
        cur += x * mul
        if cur > f:
            f = cur
        app(f)
        i += 1
    c = (-f) % M
    S = (f + c) // M
    return c, (S + num * c) // d, S


if K == 0:
    print(0)
else:
    c, fc, S = evaluate(1, 0)
    if c <= K:
        print(fc)
    else:
        c1, f1 = c, fc
        c2, f2 = 0, 0
        while True:
            d = c1 - c2
            num = f1 - f2
            c, fc, S = evaluate(d, num)
            if S == d * f1 - num * c1:
                print(f2 + num * (K - c2) // d)
                break
            if c == K:
                print(fc)
                break
            if c > K:
                c1, f1 = c, fc
            else:
                c2, f2 = c, fc
```


1585
Созвездие «Сердце»

```
from bisect import bisect_left
from itertools import accumulate

n = int(input())
W = 2001
cols = {}
rowmask = {}
rowrev = {}
for _ in range(n):
    x, y = map(int, input().split())
    cols.setdefault(x, []).append(y)
    rowmask[y] = rowmask.get(y, 0) | (1 << x)
    rowrev[y] = rowrev.get(y, 0) | (1 << (W - 1 - x))

rows_sorted = sorted(rowmask)
ans = 0

for x, ys in cols.items():
    if len(ys) < 2:
        continue
    ys.sort()
    didx = {ys[i]: i for i in range(1, len(ys))}
    start = bisect_left(rows_sorted, ys[1])
    cnt = [0] * (W + 2)
    total_e = 0
    sh1 = x + 1
    sh2 = W - x
    for k in range(len(rows_sorted) - 1, start - 1, -1):
        r = rows_sorted[k]
        M = (rowmask[r] >> sh1) & (rowrev[r] >> sh2)
        if not M:
            continue
        c = didx.get(r)
        if c and total_e:
            pref = list(accumulate(cnt))
            s = 0
            m = M
            while m:
                low = m & -m
                d = low.bit_length()
                s += pref[d - 1]
                m ^= low
            ans += c * s
        m = M
        while m:
            low = m & -m
            cnt[low.bit_length()] += 1
            total_e += 1
            m ^= low

print(ans)
```