/*****************************************
* Section : 15
* Machine No. : N
* Roll No. : 19CS100XY
* Name : Aritra Hazra
* Assignment No : 5A
* Description : Rabbit and Turtle Movement
*****************************************/

#include<stdio.h>
#include<stdlib.h>

#define MAX_RABBIT 1000
#define NO_OF_TURTLE 1

int NewPos(int position, char move)
{
    if(move == 'L')
        return position*2;
    if(move == 'R')
        return position*2 + 1;
    if((move == 'U') && (position > 1))
        return position/2;
    // else move == 'S'
    return position;
}

void OneOutArray(int array[], int length)
{
    int i;
    for(i = 0; i < length; i++) {
        array[i] = 1;
    }
}

// returns the index at which the Turtle was caught or 0 if not caught
int turtleCaught(int rabbits[], int numRabbits, int turtleIndex)
{
    int i;
    for(i = 0; i < numRabbits; i++) {
        if(rabbits[i] == turtleIndex)
            return i+1;
    }
    return 0;
}

int main() {
    int moveNum = 0;
    int turtleIndex = 0;
    int numRabbits = 0;
    int numMoves = 0;
    char turn[MAX_RABBIT+NO_OF_TURTLE+1];
    int tempPos = 0;
    int catchCheck = 0;
    int turtleCatch = 0;
    int rabbits[MAX_RABBIT];
    int i, j, k;
    
    printf("Inputs: ");
    scanf("%d %d %d",&numRabbits, &numMoves, &turtleIndex);
    OneOutArray(rabbits, numRabbits);

    printf("Outputs: ");
    if(turtleIndex == 1) {
        printf("1 1");
        turtleCatch = 1;
    }
    else {
        for(j=0; j< numMoves; j++) {
            scanf("%s", turn);
            tempPos = NewPos(turtleIndex, turn[0]);
            turtleIndex = tempPos;
            catchCheck = turtleCaught(rabbits, numRabbits, turtleIndex);
            if(catchCheck > 0) {
                printf("%d %d", j+1, catchCheck);
                turtleCatch = 1;
                break;
            }
            
            for(k=0; k < numRabbits; k++) {
                tempPos = NewPos(rabbits[k], turn[k+1]);
                rabbits[k] = tempPos;
            }
            catchCheck = turtleCaught(rabbits, numRabbits, turtleIndex);
            if(catchCheck > 0) {
                printf("%d %d", j+1, catchCheck);
                turtleCatch = 1;
                break;
            }
        }
    }
    if(!turtleCatch) {
        printf("0 0");
    }
    printf("\n");

    return 0;
}