406190: GYM102307 D Do Not Try This Problem

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Do Not Try This Problemtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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!

Input

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

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

ExampleInput
xaaaaaaaaaaaaaaaaaaa
3
4 2 8 b
6 3 4 c
10 5 2 d
Output
xaabacabcdacabdbacad

加入题单

上一题 下一题 算法标签: