#include <fstream>
#include <vector>
#include <algorithm>
#include <time.h>

#define MAXN 100000

using namespace std;

ifstream in("input.txt");

bool frakkiobello_permutation(int N, int K, int A[], int B[])
{
    sort(A, A+N);
    sort(B, B+N);
    for(int i=0; i<N; i++)
        if(A[i] != B[i])
            return false;
    return true;
}

bool my_is_permutation(int N, int K, int A[], int B[])
{
    vector<int> freq(K,0);
    for (int i=0; i<N; i++)
        freq[A[i]]++;
    for (int i=0; i<N; i++)
        freq[B[i]]--;
    for (int i=0; i<N; i++)
        if (freq[A[i]])
            return false;
    return true;
}

int main()
{
    int N, K;
    int A[MAXN];
    int B[MAXN];

    in >> N >> K;
    for (int i=0; i<N; i++)
        in >> A[i];
    for (int i=0; i<N; i++)
        in >> B[i];

    clock_t t;
    t = clock();
    cout << "Soluzione in O(N^2) fa: " << is_permutation(A,A+N,B);
    t = clock() - t;
    cout << " in " << t << " millisecondi.\n";
    t = clock();
    cout << "Soluzione in O(NlogN) fa: " << frakkiobello_permutation(N,K,A,B);
    t = clock() - t;
    cout << " in " << t << " millisecondi.\n";
    t = clock();
    cout << "Soluzione in O(N) fa: " << my_is_permutation(N,K,A,B);
    t = clock() - t;
    cout << " in " << t << " millisecondi.\n";
    return 0;
}