List of Strings

ধর তোমার কাছে একটি লিস্ট $D$ আছে। লিস্টটি শুরুতে ফাঁকা। এই প্রব্লেমে তোমাকে তিন ধরনের কাজ করতে বলা হবে লিস্টের উপর। নীচে এগুলো বর্ণনা করা হলোঃ

• 1 $S$
  এই কুয়েরিতে তুমি লিস্ট $D$ তে একটি স্ট্রিং $S$ যোগ করবে।

• $2$ $T$ $L$
  এই কুয়েরিতে তোমাকে লিস্ট $D$ এর $T$ তম স্ট্রিং থেকে $L$ দৈর্ঘ্যের সাফিক্স বাদ দিতে হবে।

• $3$ $i$ $j$
  
  $min(D_{i},D_{j}) =$ $D_{i}$ এবং $D_{j}$ এর মধ্যে যে Lexicographically ছোট
  $max(D_{i}, D_{j}) =$ $D_{i}$ এবং $D_{j}$ এর মধ্যে যে Lexicographically বড়
  
  এই কুয়েরিতে তোমাকে বের করতে হবে কতগুলো স্ট্রিং $D_{k}$আছে যারা $min(D_{i},D_{j}) \leq D_{k} \leq max(D_{i},D_{j})$ এই শর্তটি পূর্ণ করে যেখানে $1\leq k \leq |D|$।

  মনে রাখবে, এখানে আমরা দুইটি স্ট্রিং এর মধ্যে Lexicographically তুলনা করছি। Lexicographical order মানে হলো Dictionary Order । আরও জানতে এই লিংকে ক্লিক করোঃ https://en.wikipedia.org/wiki/Lexicographic_order

স্ট্রিং গুলোতে শুধুমাত্র ছোট হাতের ইংরেজি বর্ণমালা থাকবে।

Input

ইনপুটে প্রথম লাইনে তোমাকে একটি পুর্ণসংখ্যা $Q$ দেওয়া হবে যা মোট ক্যুয়েরি সংখ্যা নির্দেশ করে। পরবর্তী $Q$ লাইনের প্রত্যেকটিতে তোমাকে নিম্নোক্ত তিন ধরণের ক্যুয়েরির একটি দেওয়া হবেঃ

• $1$ $S$
  তোমার লিস্টে S যোগ করো

• $2$ $T$ $L$
  যেখানে, $1\leq T\leq |D|$ এবং $1 \leq L \leq |D_{T}|$

• $3$ $i$ $j$
  যেখানে, $1 \leq i,j \leq |D|$

  $Constraints:$
  সাবটাস্ক 1: 10 পয়েন্ট এর জন্য

  • $1 \leq Q \leq 300$

  • $1 \leq |S| \leq 10$

  • $1 \leq \sum(|D_{i}|) \leq 100$

  • এই টাস্কে Type 2 এর কোন কুয়েরি থাকবেনা।

  সাবটাস্ক 2: 90 পয়েন্ট এর জন্য

  • $1 \leq Q \leq 10^{6}$

  • $1 \leq |S| \leq 10^{5}$

  • $1 \leq \sum(|D_{i}|) \leq 10^{6}$

Output

কুয়েরি $৩$ এর জন্য স্ট্রিং-গুলোর সংখ্যা প্রিন্ট করো যারা প্রদত্ত শর্ত পূরণ করে।

Samples

Input	Output
5 1 aa 1 aaa 1 aaaa 2 2 2 3 1 3	2

Input	Output
8 1 abc 1 defg 3 1 2 1 hijkl 3 2 3 2 2 1 2 2 3 3 2 3	2 2 3
After executing the $7^{th}$query, the list is $D$ $=$ [ “abc“, ““,”hijkl” ]. So, the answer to the $8^{th}$query is $3$.