### L题：L is the Only Lovely Problem

emmm 签到题

import sys

if s[:6] == "lovely": print("lovely")
else: print("ugly")

### B题：Classical String Problem

Given a string S consists of lower case letters. You're going to perform Q operations one by one. Each operation can be one of the following two types:

• Modify: Given an integer x. You need to modify S according to the value of x. If x is positive, move the leftmost x letters in S to the right side of S; otherwise, move the rightmost |x| letters in S to the left side of S.
• Answer: Given a positive integer x. Please answer what the x-th letter in the current string S is.

import sys

idx,p = 0,len(s)
for _ in range(n):
b = int(b)
if a == "A": print(s[(idx + b - 1) % p])
else: idx = (idx + b) % p

### A题： Clam and Fish

There is a fishing game as following:

• The game contains n stages, numbered from 1 to n.

• There are four types of stages (numbered from 0 to 3):

type 0: There are no fish and no clam in this stage.

type 1: There are no fish and one clam in this stage.

type 2: There are one fish and no clam in this stage.

type 3: There are one fish and one clam in this stage.

In each stage, you can do exactly one of the following four actions.

1. If there is a clam in the stage, you can use this clam to make one pack of fish bait. And the number of packs of fish bait you have is increased by one.  You can use this pack of fish bait to catch fish after this stage.

2. If there is one fish in the stage, you can catch this fish without any fish bait. After this stage, the number of packs of fish bait you have is not changed.

3. If you have at least one pack of fish bait. You can always catch one fish by using exactly one pack of fish bait even if there are no fish in this stage. After this stage, the number of packs of fish bait you have is decreased by one.

4. You can do nothing.

Now, you are given nnn and the type of each stage. Please calculate the largest number of fish you can get in the fishing game.

import sys

while t > 0:
t -= 1
cnt = *(len(s))
cnt[len(s) - 1] =  0
for i in range(len(s)-2,-1,-1):
cnt[i] = cnt[i+1] + 1 if s[i+1] == '2' or s[i+1] == '3' else cnt[i+1]
bait,ans = 0,0
for i in range(len(s)):
if s[i] == '2' or s[i] == '3': ans += 1
elif s[i] == '1':
if len(s) - i - 1 - cnt[i] <= bait and bait != 0:
bait -= 1
ans += 1
else: bait += 1
else:
if bait != 0:
bait -= 1
ans += 1
print(ans)

### F题：Fraction Construction Problem

There are t queries.
In each query, you are given two positive integers a and b (a,b<2e6)
Please print a line consists of four positive integers c,d,e,f satisfying the following constraints:

• • d < b and f < b
• 1 <= c,e <= 4e12

If there are multiple solutions, you can print anyone.

If there are no solution, please print "-1 -1 -1 -1" in this line.

import sys

def gcd(a, b):
while b != 0:
a, b = b, a % b
return a

def exgcd(a, b):
if b == 0: return (a, 1, 0)
d_, x_, y_ = exgcd(b, a%b)
d,x,y = d_, y_, x_-a//b*y_
return (d,x,y)

while t > 0:
t -= 1
if b == 1:
print(-1,-1,-1,-1)
continue
gc = gcd(a,b)
if gc != 1:
print((a+b)//gc, b//gc, 1, 1)
continue
d,f = 2,b
while d*d <= b:
if b % d == 0 and gcd(d,b//d) == 1:
f = b // d
break  # 穷举法求素因子
d += 1
if f == b:
print(-1,-1,-1,-1)
continue
r, x, y = exgcd(f, d) # 解方程
x, y = x * a, y * a  # 求 =a 的解
if x > 0 and y < 0: print(x,d,-y,f)
else: print(y,f,-x,d)