int findKth(vector<int> &A,vector<int>&B, int startA,int startB,int k){
    int lenA=A.size()-startA;
    int lenB=B.size()-startB;
    int(lenA>lenB)
        return findKth(B,A,startB,startA,k);
    if(lenA==0)
        return B[startB+k-1];
    if(k==1)
        return min(A[startA],B[startB]);
    int pa=min(k/2,lenA);
    int pb=k-pa;
    if(A[startA+pa-1]>B[startB+pb-1])
        return findKth(A,B,startA,startB+pb,k-pb);
    else if(A[startA+pa-1]<B[startB+pb-1])
        return findKth(A,B,startA+pa,startB,k-pa);
    return A[startA+pa-1];
}
int findKth(vector<int>&A,vector<int>&B,int k){
    if(k<1||k>A.size()+B.size())
        throw runtime_error("k is illegal");
    return findKth(A,B,0,0,k);
}