406190: GYM102307 D Do Not Try This Problem

Mr. Potato Head has given you a string $$$s$$$ of length $$$n$$$ and a list of $$$q$$$ operations. Each operation is defined by three integers $$$i$$$, $$$a$$$ and $$$k$$$, and a character $$$c$$$. To complete an operation on a string $$$s$$$, you must replace $$$s_i$$$, $$$s_{i+a}$$$, $$$s_{i+2a}, \ldots$$$ and $$$s_{i+ka}$$$ with the character $$$c$$$. In order to impress Mr. Potato Head, you will write a program that will perform all of this operations, in the order they are given, and print the resulting string. If this program runs in under 2 seconds, using less than 256MB of memory, then Mr. Potato Head will be in awe!

The first line contains a single string $$$s$$$. $$$s$$$ consists of lowercase English letters and has length $$$n$$$ ($$$1 < n \leq 10^5$$$).

The second line contains a single integer $$$q$$$ ($$$1 \leq q \leq 10^5$$$).

Each of the next $$$q$$$ lines contains $$$i$$$, $$$a$$$, $$$k$$$ and $$$c$$$, in this order, and defines an operation. $$$1 \leq i \leq n$$$, $$$1 \leq a < n$$$, $$$0 \leq k < n$$$ and $$$i + ka \leq n$$$. $$$c$$$ is a lowercase English letter.

Output a single line containing the resulting string after sequentially completing all the operations on the string Mr. Potato Head gave you.

xaaaaaaaaaaaaaaaaaaa
3
4 2 8 b
6 3 4 c
10 5 2 d

xaabacabcdacabdbacad