CF1729F Kirei and the Linear Function

Given the string $ s $ of decimal digits (0-9) of length $ n $ . A substring is a sequence of consecutive characters of a string. The substring of this string is defined by a pair of indexes — with its left and right ends. So, each pair of indexes ( $ l, r $ ), where $ 1 \le l \le r \le n $ , corresponds to a substring of the string $ s $ . We will define as $ v(l,r) $ the numeric value of the corresponding substring (leading zeros are allowed in it). For example, if $ n=7 $ , $ s= $ "1003004", then $ v(1,3)=100 $ , $ v(2,3)=0 $ and $ v(2,7)=3004 $ . You are given $ n $ , $ s $ and an integer $ w $ ( $ 1 \le w < n $ ). You need to process $ m $ queries, each of which is characterized by $ 3 $ numbers $ l_i, r_i, k_i $ ( $ 1 \le l_i \le r_i \le n; 0 \le k_i \le 8 $ ). The answer to the $ i $ th query is such a pair of substrings of length $ w $ that if we denote them as $ (L_1, L_1+w-1) $ and $ (L_2, L_2+w-1) $ , then: - $ L_1 \ne L_2 $ , that is, the substrings are different; - the remainder of dividing a number $ v(L_1, L_1+w-1) \cdot v(l_i, r_i) + v(L_2, L_2 + w - 1) $ by $ 9 $ is equal to $ k_i $ . If there are many matching substring pairs, then find a pair where $ L_1 $ is as small as possible. If there are many matching pairs in this case, then minimize $ L_2 $ . Note that the answer may not exist.

N/A

N/A

Consider the first test case of example inputs. In this test case $ n=7 $ , $ s= $ "1003004", $ w=4 $ and one query $ l_1=1 $ , $ r_1=2 $ , $ k_1=1 $ . Note that $ v(1,2)=10 $ . We need to find a pair of substrings of length $ 4 $ such that $ v(L_1, L_1+3)\cdot10+v(L_2,L_2+3) $ has a remainder of $ k_1=1 $ when divided by $ 9 $ . The values $ L_1=2, L_2=4 $ actually satisfy all the requirements: $ v(L_1, L_1+w-1)=v(2,5)=30 $ , $ v(L_2, L_2+w-1)=v(4,7)=3004 $ . Indeed, $ 30\cdot10+3004=3304 $ , which has a remainder of $ 1 $ when divided by $ 9 $ . It can be shown that $ L_1=2 $ is the minimum possible value, and $ L_2=4 $ is the minimum possible with $ L_1=2 $ .