UVA 11385

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
long long int fibonacci[46];
void findFibonaccis() {
    int n;
    fibonacci[0]=1;
    fibonacci[1]=1;
    for (n=2;n<46;n++) fibonacci[n]=fibonacci[n-2]+fibonacci[n-1];
}
int findFibo(long long int array[], int n, int item){
    int i, first, last, middle;
    first = 0;
    last = n - 1;
    middle = (first + last) / 2;
    while( first <= last ){
        if(array[middle] < item) first = middle + 1;
        else if(array[middle] == item) return middle;
        else last = middle - 1;
        middle = (first + last) / 2;
    }
    if(first > last) return -1;
}

int main() {
    findFibonaccis();
    int T;
    cin >> T;
    while (T--) {
        int rank[45];
        int N,i,j,k;
        char str[45], ansstr[45];
        cin >> N;
        for(i=0;i<N;i++) cin >> rank[i];
        cin >> str;
        for (i=0;i<N;i++) {
            int position = findFibo(fibonacci, 46, rank[i]);
            printf("%d\n", position);
            if (str[i] >= 'A'&& str[i] <='Z' && position >=0) ansstr[position] = str[i];
            else ansstr[position] = ' ';
        }
        ansstr[i+1]='\0';
        cout << ansstr << endl;
    }

    return 0;
}