디퍼와 장치

디퍼가 오늘 다락방에서 이상한 장치를 발견했다. 장치에는 1번부터 $n$번까지 번호가 붙은 슬롯이 차례로 놓여 있다. 각 슬롯에는 문자열이 하나씩 들어 있고, 처음에는 모든 슬롯이 빈 문자열이다. 장치는 $l$, $r$, $s$가 주어지면 $l$번 슬롯부터 $r$번 슬롯까지 모든 문자열의 끝에 문자열 $s$를 덧붙인다.

디퍼는 메이블이 장치의 동작을 모델링할 수 없다고 내기를 걸었다. 디퍼가 명령을 내리면 메이블은 같은 명령을 동시에 따라 한다. 메이블이 장치의 동작을 정확히 재현하는지 확인하기 위해 디퍼는 가끔 다음 질문을 한다. 슬롯 $i$의 문자열에서 $x$번째 문자부터 $y$번째 문자까지의 부분 문자열은 무엇인가? 메이블은 이 과정을 시뮬레이션하는 프로그램을 작성하려고 한다. 이를 도와 달라.

첫 줄에 두 자연수 $n$, $m$이 주어진다. $n$은 슬롯의 개수이고, $m$은 디퍼의 명령 개수이다 ($1 \le n \le 2 \cdot 10^5$; $1 \le m \le 2 \cdot 10^5$).

다음 $m$개의 줄에 명령이 한 줄에 하나씩 주어진다. 명령은 다음 두 종류 중 하나이다.

• 1 $l$ $r$ $s$: $l$번 슬롯부터 $r$번 슬롯까지 모든 문자열의 끝에 비어 있지 않은 문자열 $s$를 덧붙인다 ($1 \le l \le r \le n$). 문자열 $s$는 영어 소문자로만 이루어져 있다.
• 2 $i$ $x$ $y$: $i$번 슬롯의 문자열에서 $x$번째 문자부터 $y$번째 문자까지의 부분 문자열을 구한다 ($1 \le i \le n$; $1 \le x \le y$). 슬롯 $i$의 문자열 길이는 항상 $y$ 이상이다.

1번 종류 명령에 주어지는 문자열 길이의 합은 $10^6$을 넘지 않는다. 2번 종류 명령에서 구하는 부분 문자열 길이의 합은 $10^6$을 넘지 않는다.

2번 종류 명령마다 답을 별도의 줄에 출력한다.