import static java.lang.System.err;
import java.util.Arrays;
import java.util.Random;
import java.util.function.LongBinaryOperator;
import java.util.function.LongUnaryOperator;
import java.util.stream.IntStream;
public class Main {
public static void main(String[] args) {
java.io.PrintWriter out = new java.io.PrintWriter(System.out);
new Main(out);
out.flush();
err.flush();
}
/*
* 1. k=Nのとき: 2択
* 2. k> 1; ++i) {
A[i] ^= A[N - i - 1];
A[N - i - 1] ^= A[i];
A[i] ^= A[N - i - 1];
}
yes |= Arrays.equals(A, B);
out.println(yes ? "Yes" : "No");
} else if (N == k + 1) {
int[] A2 = Arrays.copyOf(A, A.length * 2);
System.arraycopy(A, 0, A2, A.length, A.length);
RollingHash BHash = RollingHash.create(B);
long base = BHash.base();
RollingHash A2Hash = RollingHash.create(A2, base);
for (int i = 0; i < A.length; ++i) {
if (A2Hash.subList(i, i + A.length).equals(BHash)) {
out.println("Yes");
return;
}
}
for (int i = 0; i < N >> 1; ++i) {
A[i] ^= A[N - i - 1];
A[N - i - 1] ^= A[i];
A[i] ^= A[N - i - 1];
}
A2 = Arrays.copyOf(A, A.length * 2);
System.arraycopy(A, 0, A2, A.length, A.length);
A2Hash = RollingHash.create(A2, base);
for (int i = 0; i < A.length; ++i) {
if (A2Hash.subList(i, i + A.length).equals(BHash)) {
out.println("Yes");
return;
}
}
out.println("No");
} else {
Arrays.sort(A);
Arrays.sort(B);
out.println(Arrays.equals(A, B) ? "Yes" : "No");
}
}
}
}
/**
* 数列に対するローリングハッシュを求めます。
*
* ローリングハッシュとは、基数{@code base}と法{@code mod}が与えられたとき、数列{@code S}に対して以下のように定義される値です。
*
hash = sum[i=1, |S|]S_i * base^(i-1) (modulo mod)
* これは、数列{@code S}を{@code base}進数で表して{@code mod}で余りを取ったものと考えることができます。
*
* @author 31536000
*
*/
interface RollingHash extends Comparable {
/**
* このローリングハッシュで用いられている基数を返します。
* @return 基数
*/
long base();
/**
* このローリングハッシュで用いられている法を返します。
* @return 法
*/
long mod();
/**
* この数列全体のハッシュを返します。
* @return 数列のハッシュ値
*/
long hash();
/**
* この数列の先頭からindex番目までのハッシュ値を返します。
* @param index ハッシュ値を求めたい区間
* @return 数列の先頭からn番目までのハッシュ値
* @exception IllegalArgumentException {@code 0 > index || index > size()}
*/
default long hash(int index) {
return hash(0, index);
}
/**
* この数列のfromIndex番目からtoIndex番目までのハッシュ値を返します。
* @param fromIndex ハッシュ値を求める区間の左端(これを含む)
* @param toIndex ハッシュ値を求める区間の右端(これを含まない)
* @return 数列のfromIndex番目からtoIndex番目までのハッシュ値
* @exception IllegalArgumentException {@code 0 > fromIndex || fromIndex > toIndex || toIndex > size()}
*/
default long hash(int fromIndex, int toIndex) {
if (0 > fromIndex || fromIndex > toIndex || toIndex > size())
throw new IllegalArgumentException("[" + fromIndex + ", " + toIndex + ") is illegal range");
return subList(fromIndex, toIndex).hash();
}
/**
* この数列の先頭からindex番目までのハッシュ値を返します。
* @param index ハッシュ値を求めたい区間
* @return 数列の先頭からn番目までのハッシュ値
* @exception IllegalArgumentException {@code 0 > index || index > size()}
*/
default RollingHash subList(int index) {
return subList(0, index);
}
/**
* この数列のfromIndex番目からtoIndex番目までのハッシュ値を返します。
* @param fromIndex ハッシュ値を求める区間の左端(これを含む)
* @param toIndex ハッシュ値を求める区間の右端(これを含まない)
* @return 数列のfromIndex番目からtoIndex番目までのハッシュ値
* @exception IllegalArgumentException {@code 0 > fromIndex || fromIndex > toIndex || toIndex > size()}
*/
RollingHash subList(int fromIndex, int toIndex);
/**
* 二つの数列をこの順に結合したときのハッシュ値を返します。
* @param l 左側の数列
* @param r 右側の数列
* @return 数列{@code l}, {@code r}をこの順に結合したときのハッシュ値
* @exception IllegalArgumentException {@code l.base() != r.base() || l.mod() != r.mod()}
* @exception NullPointerException {@code l == null || r == null}
*/
RollingHash merge(RollingHash l, RollingHash r);
/**
* この数列の長さを返します。
* @return 数列長
*/
int size();
/**
* 二つの数列の最長共通接頭辞の長さを求めます。
* @param l 数列
* @param r 数列
* @return {@code l}と{@code r}の最長共通接頭辞
* @exception IllegalArgumentException {@code l.base() != r.base() || l.mod() != r.mod()}
* @exception NullPointerException {@code l == null || r == null}
*/
static int lcp(RollingHash l, RollingHash r) {
if (l == null || r == null) throw new NullPointerException();
if (l.base() != r.base() || l.mod() != r.mod()) throw new IllegalArgumentException();
int min = 0, max = Math.min(l.size(), r.size()) + 1;
while (max - min > 1) {
int mid = min + (max - min >> 1);
if (l.hash(mid) == r.hash(mid)) min = mid;
else max = mid;
}
return min;
}
/**
* 二つの数列の最長共通接頭辞の長さを求めます。
* @param S 数列
* @return 自身と{@code S}の最長共通接頭辞
* @exception IllegalArgumentException {@code base() != S.base() || mod() != S.mod()}
* @exception NullPointerException {@code S == null}
*/
default int lcp(RollingHash S) {
return lcp(this, S);
}
@Override
default int compareTo(RollingHash o) {
int lcp = lcp(this, o);
if (size() == lcp) { return o.size() == lcp ? 0 : -1; }
if (o.size() == lcp) return 1;
return Long.compare(hash(lcp, lcp + 1), o.hash(lcp, lcp + 1));
}
/**
* この数列の中に{@code s}を連続部分列として含む場合、その先頭のインデックスを返します。そのようなものが無い場合、{@code -1}を返します。
* @param s 調べる数列
* @return {@code s}を連続部分列として含む場合はその先頭のインデックス、無ければ{@code -1}
* @exception IllegalArgumentException {@code base() != s.base() || mod() != s.mod()}
* @exception NullPointerException {@code s == null}
*/
default int find(RollingHash s) {
if (s == null) throw new NullPointerException();
if (base() != s.base() || mod() != s.mod()) throw new IllegalArgumentException();
int size = s.size();
long hash = s.hash();
for (int i = 0, l = size() - size; i <= l; ++i) {
if (hash(i, i + size) == hash) return i;
}
return -1;
}
/**
* 数列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
* @param S 各要素が0以上2^{61}-1未満の数列
* @return {@code S}のローリングハッシュ
*/
static RollingHash create(long[] S) {
Random rnd = new Random();
long MOD = (1L << 61) - 1;
long MASK0 = (1L << 30) - 1;
long MASK1 = (1L << 31) - 1;
LongUnaryOperator mod = x -> {
final long xu = x >>> 61;
final long xd = x & MOD;
long res = xu + xd;
if (res >= MOD) res -= MOD;
return res;
};
LongBinaryOperator mul = (a, b) -> {
final long au = a >>> 31;
final long ad = a & MASK1;
final long bu = b >>> 31;
final long bd = b & MASK1;
final long mid = ad * bu + au * bd;
final long midu = mid >>> 30;
final long midd = mid & MASK0;
return mod.applyAsLong((au * bu << 1) + midu + (midd << 31) + ad * bd);
};
LongBinaryOperator gcd = (a, b) -> {
while (a != 0) if ((b %= a) != 0) a %= b;
else return a;
return b;
};
while (true) {
long e = mod.applyAsLong(rnd.nextLong());
if (gcd.applyAsLong(e, MOD - 1) == 1) {
long base = 1;
for (long x = 37; e > 0; e >>= 1, x = mul.applyAsLong(x, x))
if ((e & 1) != 0) base = mul.applyAsLong(base, x);
return create(S, base);
}
}
}
/**
* 数列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
* @param S 数列
* @return {@code S}のローリングハッシュ
*/
static RollingHash create(int[] S) {
return create(Arrays.stream(S).mapToLong(i -> i).toArray());
}
/**
* 文字列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
* @param S 文字列
* @return {@code S}のローリングハッシュ
*/
static RollingHash create(char[] S) {
return create(IntStream.range(0, S.length).mapToLong(i -> S[i]).toArray());
}
/**
* 文字列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
* @param S 文字列
* @return {@code S}のローリングハッシュ
*/
static RollingHash create(String S) {
return create(IntStream.range(0, S.length()).mapToLong(S::charAt).toArray());
}
/**
* 数列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
* @param S 各要素が0以上2^{61}-1未満の数列
* @param base 基数
* @return {@code S}のローリングハッシュ
*/
static RollingHash create(long[] S, long base) {
long MOD = (1L << 61) - 1;
class DefaultRollingHash implements RollingHash {
final long[] hash;
final long[] pow;
static final long MASK0 = (1L << 30) - 1;
static final long MASK1 = (1L << 31) - 1;
final int len = S.length;
long mod(final long x) {
final long xu = x >>> 61;
final long xd = x & MOD;
long res = xu + xd;
if (res >= MOD) res -= MOD;
return res;
}
long mul(final long a, final long b) {
final long au = a >>> 31;
final long ad = a & MASK1;
final long bu = b >>> 31;
final long bd = b & MASK1;
final long mid = ad * bu + au * bd;
final long midu = mid >>> 30;
final long midd = mid & MASK0;
return mod((au * bu << 1) + midu + (midd << 31) + ad * bd);
}
DefaultRollingHash() {
hash = new long[S.length + 1];
pow = new long[S.length + 1];
pow[0] = 1;
for (int i = 0; i < S.length; ++i) {
hash[i + 1] = mod(mul(hash[i], base) + S[i]);
pow[i + 1] = mul(pow[i], base);
}
}
@Override
public long base() {
return base;
}
@Override
public long mod() {
return MOD;
}
@Override
public long hash() {
return hash[hash.length - 1];
}
@Override
public long hash(int fromIndex, int toIndex) {
return mod(hash[toIndex] - mul(hash[fromIndex], pow[toIndex - fromIndex]) + MOD);
}
@Override
public RollingHash subList(int fromIndex, int toIndex) {
class SubRollingHash implements RollingHash {
final int l, r;
final long hash;
SubRollingHash(int l, int r) {
this.l = l;
this.r = r;
hash = DefaultRollingHash.this.hash(l, r);
}
private void check(int from, int to) {
if (0 > from || from > to || to > r - l) throw new IllegalArgumentException(
"[" + from + ", " + to + ") is out of range: [0, " + (r - l) + ")");
}
@Override
public long base() {
return base;
}
@Override
public long mod() {
return MOD;
}
@Override
public long hash() {
return hash;
}
@Override
public long hash(int fromIndex, int toIndex) {
check(fromIndex, toIndex);
return DefaultRollingHash.this.hash(l + fromIndex, l + toIndex);
}
@Override
public RollingHash subList(int fromIndex, int toIndex) {
check(fromIndex, toIndex);
return new SubRollingHash(l + fromIndex, l + toIndex);
}
@Override
public RollingHash merge(RollingHash l, RollingHash r) {
return merge(l, r);
}
@Override
public int size() {
return r - l;
}
@Override
public int hashCode() {
return Long.hashCode(hash());
}
@Override
public boolean equals(Object o) {
if (o instanceof RollingHash) {
RollingHash hash = (RollingHash) o;
return hash() == hash.hash();
}
return false;
}
}
return new SubRollingHash(fromIndex, toIndex);
}
@Override
public RollingHash merge(RollingHash l, RollingHash r) {
class MergeRollingHash implements RollingHash {
final RollingHash l, r;
final long hash;
final int size;
MergeRollingHash(RollingHash l, RollingHash r) {
this.l = l;
this.r = r;
hash = DefaultRollingHash.this.mod(mul(l.hash(), pow[r.size()]) + r.hash());
size = l.size() + r.size();
}
@Override
public long base() {
return base;
}
@Override
public long mod() {
return MOD;
}
@Override
public long hash() {
return hash;
}
@Override
public RollingHash subList(int fromIndex, int toIndex) {
if (0 > fromIndex || fromIndex > toIndex || toIndex > size())
throw new IllegalArgumentException(
"[" + fromIndex + ", " + toIndex + ") is out of range: [0, " + size() + ")");
if (toIndex <= l.size()) return l.subList(fromIndex, toIndex);
if (fromIndex >= l.size()) return r.subList(fromIndex - l.size(), toIndex - l.size());
return merge(l.subList(fromIndex, l.size()), r.subList(0, toIndex - l.size()));
}
@Override
public RollingHash merge(RollingHash l, RollingHash r) {
return new MergeRollingHash(l, r);
}
@Override
public int size() {
return size;
}
@Override
public int hashCode() {
return Long.hashCode(hash());
}
@Override
public boolean equals(Object o) {
if (o instanceof RollingHash) {
RollingHash hash = (RollingHash) o;
return hash() == hash.hash();
}
return false;
}
}
return new MergeRollingHash(l, r);
}
@Override
public int size() {
return len;
}
@Override
public int hashCode() {
return Long.hashCode(hash());
}
@Override
public boolean equals(Object o) {
if (o instanceof RollingHash) {
RollingHash hash = (RollingHash) o;
return hash() == hash.hash();
}
return false;
}
}
return new DefaultRollingHash();
}
/**
* 数列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
* @param S 数列
* @param base 基数
* @return {@code S}のローリングハッシュ
*/
static RollingHash create(int[] S, long base) {
return create(Arrays.stream(S).mapToLong(i -> i).toArray(), base);
}
/**
* 文字列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
* @param S 文字列
* @param base 基数
* @return {@code S}のローリングハッシュ
*/
static RollingHash create(char[] S, long base) {
return create(IntStream.range(0, S.length).mapToLong(i -> S[i]).toArray(), base);
}
/**
* 文字列{@code S}に対して2^{61}-1を法とするローリングハッシュを計算します。
* @param S 文字列
* @param base 基数
* @return {@code S}のローリングハッシュ
*/
static RollingHash create(String S, long base) {
return create(IntStream.range(0, S.length()).mapToLong(S::charAt).toArray(), base);
}
}