G - String Rotation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

長さ N の英小文字からなる文字列 S=S_1S_2\dots S_N が与えられます。あなたは、S に対して以下の操作をちょうど 1 回行います。

  • S の長さ 1 以上の連続部分文字列を選んで、左に 1 だけ巡回シフトする。すなわち、整数 1 \leq \ell \leq r \leq N を選んで、S の r 文字目の右に S_\ell を挿入したのち、S の \ell 番目の文字を削除する。

操作後の S としてありえる文字列のうち、辞書順最小のものを求めてください。

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

  • 1 \leq T \leq 10^5
  • 1 \leq N \leq 10^5
  • S は英小文字からなる長さ N の文字列
  • T,N は整数
  • 1 つの入力ファイルに含まれる N の総和は 10^5 以下

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケース \mathrm{case}_i\;(1 \leq i \leq T) は以下の形式で与えられる。

N
S

出力

T 行出力せよ。i \; (1 \leq i \leq T) 行目には、\mathrm{case}_i に対する答えを出力せよ。

入力例 1

3
7
atcoder
1
x
5
snuke

出力例 1

acodert
x
nsuke
  • 1 番目のテストケースでは、2 文字目から 7 文字目を巡回シフトして acodert とするのが辞書順最小です。
  • 2 番目のテストケースでは、どのように操作しても x が得られます。
  • 3 番目のテストケースでは、1 文字目から 2 文字目を巡回シフトして nsuke とするのが辞書順最小です。

Score : 400 points

Problem Statement

You are given a string S=S_1S_2\dots S_N of length N consisting of lowercase English letters. You will perform the following operation on S exactly once:

  • Choose a contiguous substring of S with length at least 1 and cyclically shift it to the left by 1. That is, choose integers 1 \leq \ell \leq r \leq N, insert S_\ell to the right of the r-th character of S, and then delete the \ell-th character of S.

Find the lexicographically smallest string among all possible strings that S can become after the operation.

You are given T test cases, so solve each of them.

Constraints

  • 1 \leq T \leq 10^5
  • 1 \leq N \leq 10^5
  • S is a string of length N consisting of lowercase English letters.
  • T and N are integers.
  • The sum of N over all test cases in a single input file is at most 10^5.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case \mathrm{case}_i\;(1 \leq i \leq T) is given in the following format:

N
S

Output

Output T lines. The i-th (1 \leq i \leq T) line should contain the answer for \mathrm{case}_i.

Sample Input 1

3
7
atcoder
1
x
5
snuke

Sample Output 1

acodert
x
nsuke
  • In the first test case, cyclically shifting from the 2nd to the 7th character gives acodert, which is lexicographically smallest.
  • In the second test case, no matter how you operate, you get x.
  • In the third test case, cyclically shifting from the 1st to the 2nd character gives nsuke, which is lexicographically smallest.