You have an array $$$A$$$ of $$$N$$$ empty strings and $$$M$$$ queries ($$$1 <= N, M <= 2*10^5$$$). There are two types queries:

1) You are given two numbers $$$L, R (1<=l<=R<=N)$$$ and a string $$$S$$$. You need to push back string $$$S$$$ to all strings in array's segment from $$$L$$$ to $$$R$$$.

2) You are given three numbers $$$I, L, R (1<=I<=N, L<=R<= |a[I]|)$$$. You need to print the substring $$$[L; R]$$$ of the string $$$A[I]$$$.

The sum of string lengths is less than $$$10^6$$$.