You are given a tree of $$$N<=10^6$$$ vertices. Each vertex of the tree contains a number $$$a[i]<=10^9$$$.You are given $$$M<=10^6$$$ queries: "Find the distance to nearest vertex to the vertex $$$V$$$, with the value less than $$$X<=10^9$$$?"

How this problem can be solved?

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$$$.