// Session 35: exhaustive natural-order mod-29 previous-plaintext recurrence.
// Compile: g++ -O3 -std=c++17 plaintext_feedback_search.cpp -o search
// Input: 27000 word-model log scores; task count; per task n, word count,
// reference a,b,k,seed; n cipher values; word lengths. Output JSON lines.
#include <algorithm>
#include <array>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stdexcept>
#include <vector>
using Key=std::array<int,4>;
using Candidate=std::pair<double,Key>;
int main(int argc,char**argv){
 if(argc!=2)return 2;
 std::ifstream in(argv[1]); std::vector<double> logp(27000);
 for(auto &x:logp)in>>x;
 int tasks;in>>tasks;std::cout<<std::setprecision(17);
 for(int task=0;task<tasks;++task){
  int n,nw;Key ref;in>>n>>nw;for(auto &x:ref)in>>x;
  std::vector<int> c(n),lengths(nw),end(n,0),base(n);
  for(auto &x:c)in>>x;int cursor=0;
  for(auto &x:lengths){in>>x;cursor+=x;if(cursor<=n)end[cursor-1]=1;}
  if(!in||cursor!=n||n<1)throw std::runtime_error("Bad input");
  auto score=[&](const Key&key){
   int state=key[3],u=29,v=29;double sum=0;
   for(int i=0;i<n;++i){
    int p=(key[0]*c[i]+key[1]*state+key[2])%29;state=p;
    sum+=logp[(u*30+v)*30+p];u=v;v=p;
    if(end[i]){sum+=logp[(u*30+v)*30+29];u=29;v=29;}
   }
   return sum/double(n+nw);
  };
  double reference=score(ref);unsigned long long count=0,above=0;
  std::priority_queue<Candidate,std::vector<Candidate>,std::greater<Candidate>> best;
  for(int a=1;a<29;++a)for(int b=1;b<29;++b)for(int k=0;k<29;++k){
   for(int i=0;i<n;++i)base[i]=(a*c[i]+k)%29;
   for(int seed=0;seed<29;++seed){
    int state=seed,u=29,v=29;double sum=0;
    for(int i=0;i<n;++i){
     int p=(base[i]+b*state)%29;state=p;
     sum+=logp[(u*30+v)*30+p];u=v;v=p;
     if(end[i]){sum+=logp[(u*30+v)*30+29];u=29;v=29;}
    }
    double s=sum/double(n+nw);++count;if(s>reference+1e-12)++above;
    Candidate cand{s,{a,b,k,seed}};
    if(best.size()<20)best.push(cand);
    else if(cand>best.top()){best.pop();best.push(cand);}
   }
  }
  std::vector<Candidate> ordered;while(!best.empty()){ordered.push_back(best.top());best.pop();}
  std::sort(ordered.rbegin(),ordered.rend());
  std::cout<<"{\"task\":"<<task<<",\"settings\":"<<count<<",\"reference_score\":"<<reference
   <<",\"reference_rank\":"<<above+1<<",\"top\":[";
  bool first=true;for(auto &cand:ordered){if(!first)std::cout<<",";first=false;
   std::cout<<"{\"prefix_score\":"<<cand.first<<",\"key\":[";
   for(int j=0;j<4;++j){if(j)std::cout<<",";std::cout<<cand.second[j];}std::cout<<"]}";
  }
  std::cout<<"]}"<<std::endl;
 }
}