/* single word (4) or double word (8) alignment */
#define ALIGNMENT 8

/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)


#define WSIZE 4 //word and header/footer size
#define DSIZE 8 //double word size (bytes)

#define INITCHUNKSIZE (1<<6) //the size of extended heap 
#define CHUNKSIZE (1<<12) //extend heap 

#define MAX(x,y) ((x)>(y))?(x):(y)
#define MIN(x,y) ((x)<(y))?(x):(y)

#define PACK(size,alloc) ((size)|(alloc))

//read and write a word at addr p
#define GET(p) (*(unsigned int*)(p))
#define PUT(p,val) (*(unsigned int*)(p) = (val))

#define SET_PTR(p,ptr) (*(unsigned int*)(p) = (unsigned int)(ptr))

#define GET_SIZE(p)  (GET(p)&~0x7)
#define GET_ALLOC(p)  (GET(p)&0x1)

//given block ptr bp,compute address of its header and footer
#define HDRP(bp)  ((char*)(bp)-WSIZE)
// (char*bp)+size -wsize= next's block's bp 's position,-DSIZE,that means 
//  previous block's foot address
#define FTRP(bp)  ((char*)(bp)+GET_SIZE(HDRP(bp))-DSIZE)

#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE((char *)(bp)-WSIZE))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE((char *)(bp)-DSIZE))

#define PRED_PTR(ptr) ((char*)(ptr))
#define SUCC_PTR(ptr) ((char*)(ptr)+WSIZE)

#define PRED(ptr) (*(char **)(ptr))
#define SUCC(ptr) (*(char **)(SUCC_PTR(ptr)))

#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define LIST_SIZE 16

static void *extend_heap(size_t words);
static void *coalesce(void *bp);
static void *place(void *bp,size_t asize);
static void insert(void *bp,size_t size);
static void delete(void *bp);

/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void)
{
    void *heap;
    if((heap=mem_sbrk(4*WSIZE))==(void*)-1)
        return -1;
    
    int idx;
	
    //initialize the list
    for(idx=0;idx<LIST_SIZE;idx++){
        list[idx] = NULL;
    }
   
    //alignment padding
    //按照上图堆的结构来初始化
    PUT(heap,0);
    PUT(heap+(1*WSIZE),PACK(DSIZE,1));  //prologue header
    PUT(heap+(2*WSIZE),PACK(DSIZE,1)); //prologue footer
    PUT(heap+(3*WSIZE),PACK(0,1)); //Epilogue header

    if(extend_heap(INITCHUNKSIZE)==NULL)
        return -1;
    return 0;
}

/* 
 * mm_malloc - Allocate a block by incrementing the brk pointer.
 *     Always allocate a block whose size is a multiple of the alignment.
 */

void *mm_malloc(size_t size)
{
    //ignore spurious requeses
    if(size==0)
        return NULL;
    
    if(size<=DSIZE)
        size = 2*DSIZE;
    else
        size = ALIGN(size+DSIZE);

    int idx = 0;
    size_t ssize = size;
    void *ptr = NULL;

    while(idx<LIST_SIZE){
		//链表类的大小分别是 1 1 2 4 8 16 32...
        // 分别存储 {0},{1},{2,3},{4,5,6,7}..
        // 通过循环 ssize>>=1 与idx,找到该分配的
        //字节大小所在的链表
        //然后再内嵌一个循环，在这个链表中寻找大小适			//合的pointer
        if((ssize<=1)&&(list[idx]!=NULL)){
            ptr = list[idx];
            while(ptr&&((size>GET_SIZE(HDRP(ptr))))){
                ptr = PRED(ptr);
            }
            //如果找到了就break
            if(ptr!=NULL)
                break;
        }
        ssize>>=1;
        idx++;
    }

    //如果找不到，向系统申请额外的堆内存
    if(ptr==NULL){
        int extendsize = MAX(size,CHUNKSIZE);
        if((ptr=extend_heap(extendsize))==NULL)
            return NULL;
    }
    
    //在free块中allocate size大小的块
    ptr = place(ptr,size);

    return ptr;
}

void mm_free(void *ptr)
{
    size_t size = GET_SIZE(HDRP(ptr));

	//把该块头脚末位都标注为0，说明这一块是free
    PUT(HDRP(ptr), PACK(size, 0));
    PUT(FTRP(ptr), PACK(size, 0));

    /* 插入分离空闲链表 */
    insert_node(ptr, size);
    /* 合并 */
    coalesce(ptr);
}

//判断是否是当前引起停止信号的是否是前台进程
volatile sig_atomic_t fg_stop_or_exit;

int setpgid (pid_t pid,pgid_t pgid);

setpgid(0,0)

void eval(char *cmdline)
{
    char *argv[MAXARGS];  //argument list execve()
    char buf[MAXLINE];
    int argc;
    int bg; //whether the job is in fg or bg
    bg = parseline(cmdline,argv);
    sigset_t mask_chld,mask_all,mask_prev;
    pid_t pid;
    
    sigemptyset(&mask_chld);
    #把SIGCHLD信号赋给mask_chld
    sigaddset(&mask_chld,SIGCHLD);
    #fill所有SIG信号给mask_all
    sigfillset(&mask_all);
    strcpy(buf,cmdline);

    //empty command
    if(argv[0]==NULL){
        return ;
    }
    else if(!builtin_cmd(argv)){
		//如果不是内部函数，首先要把SIGCHLD信号阻塞住，以防出现竞争条件。
		//子进程要解决信号阻塞，并执行相关的函数
        //if the below code are outside of the buildin_cmd function,
        //then these locks won't be realeased when executing inner commands
        //block the SIGCHLD in order to prevent child process ends between father process
		//先要阻塞SIGCHLD信号
        sigprocmask(SIG_BLOCK,&mask_chld,&mask_prev);
        //codes below won't be interrupt by signal SIGCHLD

        //running a child process
        //
        if((pid=fork())==0){
         //由于子进程会继承block的特性，所以子进程要记得unblock。
            sigprocmask(SIG_SETMASK,&mask_prev,NULL);//unblock the order
            //change the process 's group, not the same as tsh's group
            setpgid(0,0);
            if(execve(argv[0],argv,environ)<0){
                printf("%s: Command not found\n",argv[0]);

            }
            //if execve cannot process then child process will execute main process
            exit(0);
        }

        //blcok all signal
        //为我阻挡一切！！就算天塌下来也要先addjob不然顺序乱就gg
        sigprocmask(SIG_BLOCK,&mask_all,NULL);
        //foreGround
        if(!bg){
            addjob(jobs,pid,FG,cmdline);
        }else{
            addjob(jobs,pid,BG,cmdline);
        }
        //block sigchld again
        sigprocmask(SIG_SETMASK,&mask_chld,NULL);

        //father process wait until front process stops
        
        
        //父进程要判断子进程是前台进程还是后台进程，如果是前台进程，则调用waitpid来等待前台进程，如果是后台，把新添加进程利用addjob添加到工作组中。
        if(!bg){
            //Block until process pid is no longer the foreground process
            waitfg(pid);
        }
        else{
            sigprocmask(SIG_BLOCK,&mask_all,NULL);
            struct job_t * currbgmask = getjobpid(jobs,pid);
            printf("[%d] (%d) %s",currbgmask->jid,currbgmask->pid,currbgmask->cmdline);
        }

        //unblock all signals
        sigprocmask(SIG_SETMASK,&mask_prev,NULL);
    }

    return;
}

int builtin_cmd(char **argv)
{

    sigset_t mask_all,mask_prev;

    sigfillset(&mask_all);

    if(!strcmp(argv[0],"quit")){
        exit(0);
    }
    else if(!strcmp(argv[0],"&")){
        return 1;
    }
    else if(!strcmp(argv[0],"jobs")){
        //when visit a global variance,you need to block all signals
        sigprocmask(SIG_BLOCK,&mask_all,&mask_prev);
        listjobs(jobs);
        sigprocmask(SIG_SETMASK,&mask_prev,NULL);
        return 1;
    }
    else if(!strcmp(argv[0],"bg")||!strcmp(argv[0],"fg")){
        do_bgfg(argv);
        return 1;
    }
    return 0;     /* not a builtin command */
}

/* 
 * waitfg - Block until process pid is no longer the foreground process
 */
 
void waitfg(pid_t pid)
{

    //fgpid return the pid of the front process id
    
    while((pid==fgpid(jobs))){
        sleep(0);
    }
    return;
}

/*
 * waitfg - Block until process pid is no longer the foreground process
 */
void waitfg(pid_t pid)
{

    sigset_t mask;
    sigemptyset(&mask);
    fg_stop_or_exit = 0;
   
    ////只有发出这个信号的子进程是前台进程才设置fg_stop_or_exit标志。
    while(!fg_stop_or_exit){
        sigsuspend(&mask);
    }

    return;
}

int kill(pid_t pid,int sig);

//如果pid大于0，那么kill函数发送信号号码sig给进程pid，如果pid==0，那么kill发送信号sig给调用进程所在进程组中的每个进程，包括调用进程自己。如果pid<0，则发送sig给进程组|pid|中的每个进程。

/*
 * sigint_handler - The kernel sends a SIGINT to the shell whenver the
 *    user types ctrl-c at the keyboard.  Catch it and send it along
 *    to the foreground job.
 */
void sigint_handler(int sig)
{

    int olderrno = errno;
    sigset_t mask_all,prev_all;
    pid_t pid;
    sigfillset(&mask_all);
    //execute global function, so block all signals
    sigprocmask(SIG_BLOCK,&mask_all,&prev_all);
    pid=fgpid(jobs);
    sigprocmask(SIG_SETMASK,&prev_all,NULL);

    //only process the front process
    //pid==0 means background process?

    if(pid!=0){
        kill(-pid,SIGINT);
        //printf("Job [%d] (%d) terminated by signal %d\n",pid2jid(pid),pid,sig);
    }

    errno = olderrno;
    return;
}

/*
 * sigtstp_handler - The kernel sends a SIGTSTP to the shell whenever
 *     the user types ctrl-z at the keyboard. Catch it and suspend the
 *     foreground job by sending it a SIGTSTP.
 */
void sigtstp_handler(int sig)
{

    pid_t pid;
    pid=fgpid(jobs);

    if(pid!=0){
        struct job_t *job = getjobpid(jobs,pid);
        if(job->state==ST)
            return;
        else
            kill(-pid,SIGTSTP);
    }

    return;
}

/*
 * sigchld_handler - The kernel sends a SIGCHLD to the shell whenever
 *     a child job terminates (becomes a zombie), or stops because it
 *     received a SIGSTOP or SIGTSTP signal. The handler reaps all
 *     available zombie children, but doesn't wait for any other
 *     currently running children to terminate.
 */

void sigchld_handler(int sig)
{
    int olderrno = errno;
    sigset_t mask_all,prev_all;
    pid_t pid;
    struct job_t *gc_job;
    int status;

    sigfillset(&mask_all);

    //尽可能回收子进程，使用WNOHANG,使得如果当前进程都没有停止的时候直接返回，
    //而不是挂起该回收进程，这样可能会阻碍无法两个短时间结束的后台进程

    while((pid = waitpid(-1,&status,WNOHANG|WUNTRACED))>0){
        sigprocmask(SIG_BLOCK,&mask_all,&prev_all);
        gc_job = getjobpid(jobs,pid);
        //说明当前引起停止的确实是前台进程
        if(pid==fgpid(jobs)){
            fg_stop_or_exit=1;
        }
        //子进程正常结束，返回一个非0值
        if(WIFEXITED(status)){
            deletejob(jobs,pid);
        }
        //子进程被暂停，只有暂停不用deletejobs
        else if(WIFSTOPPED(status)){
            //子进程停止引起waitpid函数返回,再判断该进程是否是前台进程
            gc_job->state = ST;
            printf("Job [%d] (%d) stopped by signal %d\n", gc_job->jid, gc_job->pid, WSTOPSIG(status));
        }
        //因捕获信号而终止
        else if (WIFSIGNALED(status)){
            //子进程终止引起的返回，判断是否是前台进程
            //并且判断该信号是否是未捕获的的信号
            printf("Job [%d] (%d) terminated by signal %d\n", gc_job->jid, gc_job->pid, WTERMSIG(status));
            deletejob(jobs,pid);
        }
        fflush(stdout);
        //unblock all signals
        sigprocmask(SIG_SETMASK,&prev_all,NULL);
    }
    errno = olderrno;
    return;
}

/*
 * do_bgfg - Execute the builtin bg and fg commands
 */
void do_bgfg(char **argv)
{

    //parameters
    char *para = argv[1];
    
    //lack parameters
    if(para==NULL){
        printf("%s command requires PID or %%jobid argument\n",argv[0]);
        return;
    }

    //full dirname
    char *cmd = argv[0];

    struct job_t*curr_job;
    sigset_t mask_all,mask_prev;
    int curr_jid;
    sigfillset(&mask_all);

    //first character of the paramaters
    //linux command: fg %n bring process n from background to frontground
    if(para[0]=='%'){
  
        // the argument is a job id
        curr_jid = atoi(&(para[1]));
        //mistake process2
        curr_job = getjobjid(jobs,curr_jid);
        if(curr_job==NULL)
        {
            printf("%%%d: No such job\n",curr_jid);
            return;
        }
    }

    else{
    	// the argument is a process id
        curr_jid = atoi(para);
        if(curr_jid==0){
            printf("%s: argument must be a PID or %%jobid\n",cmd);
            fflush(stdout);
            return;
        }
        //block all signals when visit global vairance
        sigprocmask(SIG_BLOCK,&mask_all,&mask_prev);
        curr_jid = pid2jid(curr_jid);
    }

    //block all signals when visit global vairance
    sigprocmask(SIG_BLOCK,&mask_all,&mask_prev);
    curr_job = getjobjid(jobs,curr_jid);

    if(curr_job==NULL){
        printf("(%s): No such process\n",para);
        fflush(stdout);
        sigprocmask(SIG_SETMASK,&mask_prev,NULL);
        return;
    }
    //bg
    if(!strcmp(cmd,"bg")){
        switch(curr_job->state){
            case ST:
                //change from stop to bg ST->BG
                //meanwhile send signal to child process
                curr_job->state =BG;
                kill(-(curr_job->pid),SIGCONT);
                printf("[%d] (%d) %s",curr_job->jid,curr_job->pid,curr_job->cmdline);
                break;
            case BG:
                break;
            case UNDEF:
            case FG:
                unix_error("bg or undef error");
                break;
        }
    }


	//要用waitfg指令，等待前台作业结束后再退出    
    else{
        switch(curr_job->state){
            //如果作业本身是STOP的话，要记得发送信号（SIGCONT，让其继续运行）
            case ST:
                //change from stop to bg ST->BG
                //meanwhile send signal to child process
                curr_job->state =FG;
                //发射信号给前台进程组，所有前台进程都会受到信号
                kill(-(curr_job->pid),SIGCONT);
                //if change to fg,then you need to wait until it dies
                waitfg(curr_job->pid);
                break;
            case BG:
                curr_job->state =FG;
                waitfg(curr_job->pid);
                break;
            case UNDEF:
            case FG:
                unix_error("bg or undef error");
                break;
        }
    }
    sigprocmask(SIG_SETMASK,&mask_prev,NULL);
    return;
}

int findLengthOfLCIS(vector<int>& nums) {
       if(nums.empty())
           return 0;
       int n = nums.size();
       int dp[n];
       dp[0]=1;
       int res = 1;
       for(int i=1;i<nums.size();i++){
           if(nums[i-1]<nums[i]){
               dp[i] = dp[i-1]+1;
           }
           else{
               dp[i] = 1;
           }
           res = max(dp[i],res);
       }
       return res;
   }

//M saves the index
int M[MAX+1];
int pre[MAX+1];
int pathIndex[MAX+1];

vector<int>vec;

void print(int pos){
    if(pos==-1)return;
    print(pre[pos]);
    cout<<" "<<vec[pos];
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int N;
    while(true){
        cin>>N;
        if(N==0)
            break;
        vec.assign(N,0);
        for(int i=0;i<N;i++){
            cin>>vec[i];
        }
        int L = 0;
        for(int i=0;i<N;i++){
            int lo = 1;
            int Hi = L;
            //find the largest mid <=L such that vec[M[mid]]<vec[i]
            while(lo<=Hi){
                int mid = ceil((lo+Hi)/2.0);
                if(vec[M[mid]]<vec[i]){
                    lo=mid+1;
                }else{
                    Hi = mid-1;
                }
            }

            //newL is 1 greater than the longest prefix of vec[i]
            int newL = lo;
            //vec[i]的前驱节点是newL-1子串的最后一个索引
            pre[i] = M[newL-1];
			//NEWL新子串的最后一个索引就是i
            M[newL] = i;

            if(newL>L)
                L = newL;
        }

        int k = M[L];
        for(int i=L-1;i>=0;i--){
            pathIndex[i] = k;
            k = pre[k];
        }
        cout<<L<<" ";
        for(int i=0;i<=L-1;i++){
            cout<<vec[pathIndex[i]]<<" ";
        }
        cout<<endl;


    }

}

int lengthOfLIS(vector<int>& nums) {
    
       if(nums.empty())
           return 0;
        int n = nums.size();
        int dp[n];
        for(int i=0;i<n;i++)
            dp[i]=1;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    //仅当dp[j]+1>dp[i]的时候才更新
                    if(dp[j]+1>dp[i]){
                        dp[i]=dp[j]+1;
                    }
                }
            }
        }
        int res = 0;
        for(int i=0;i<n;i++)
            res = max(res,dp[i]);
        return res;
    }

int lengthOfLIS(vector<int>& nums) {
    
       if(nums.empty())
           return 0;
        int n = nums.size();
        int dp[n];
        dp[0] = nums[0];
        int len=1;
        for(int i=1;i<n;i++){
            int left=0;
            int right = len-1;
            int mid;
            if(dp[len-1]<nums[i]){
                dp[len++]=nums[i];
            }else{
                while(left<=right){
                    mid = (left+right)/2;
                    if(dp[mid]<nums[i]){
                        left = mid+1;
                    }else{
                        right = mid-1;
                    }
                }
                dp[left] = nums[i];
            }
            
        }
        
        return len;
    }
};

int max_sum(vector<int>&nums,int i){
        if(i==0)
            return nums[i];
        int res = max(nums[i],nums[i]+max_sum(nums,i-1));
        return res;
    }
    
    int maxSubArray(vector<int>& nums) {
        
        if(nums.empty())
            return 0;
        int res = nums[0];
        for(int i=0;i<nums.size();i++){
            res = max(res,max_sum(nums,i));
        }
        return res;
        
        
    }

int maxSubArray(vector<int>& nums) {
      if(nums.empty())
          return 0;
      int n = nums.size();
      int dp[n];
      dp[0] = nums[0];
      int res = dp[0];
      for(int i=1;i<n;i++){
          dp[i] = nums[i]+(dp[i-1]>0?dp[i-1]:0);
          res = max(res,dp[i]);
      }
      return res;
  }

#include <iostream>
#include <cstring>

using namespace std;
#define INF 0x3f3f3f3f
int A[30][30][30];

int main(){

    int k;

    while(true){
        long long int dp[10001];
        int arr[10001];
        cin>>k;
        if(k==0)
            break;
        int posFlag = 0;
        for(int i=1;i<=k;i++){
            scanf("%d",&arr[i]);
            if(arr[i]>=0)
                posFlag=1;
        }
        if(posFlag!=1){
            cout<<0<<" "<<arr[1]<<" "<<arr[k]<<endl;
        }
        else{
            double max = -INF;
            dp[1]=arr[1];
            int resulti=1;
            for(int i=1;i<=k;i++){
                //or dp[i] = max(dp[i-1]+arr[i],arr[i])
                dp[i] = arr[i]+(dp[i-1]>0?dp[i-1]:0);
                if(dp[i]>max){
                    max = dp[i];
                    resulti = i;
                }
            }
            double max2=0;
            int start=1;
            for(int i=resulti;i>=1;i--){
                max2+=arr[i];
                if(max2==max){
                    start = i;
                    break;
                }
            }
            cout<<max<<" "<<arr[start]<<" "<<arr[resulti]<<endl;
        }

    }

}

string a="bananinn";
string b = "kaninan";

int lcs(int i,int j){
    if(i==-1||j==-1)
        return 0;


    int res=0;
    res = max(res,lcs(i-1,j));
    res = max(res,lcs(i,j-1));

    if(a[i]==b[j]){
        res = max(res,1+lcs(i-1,j-1));
    }
    return res;
}

int main(){
    int mem[1000][1000];
    memset(mem,-1,sizeof(mem));
    int ans = 0;
    for(int i=0;i<8;i++){
        for(int j=0;j<7;j++){
            ans = max(ans,lcs(i,j));
        }
    }
    cout<<ans<<endl;
}

Dynamic programming formulation
map<problem, value> memory;
	value dp(problem P) {
		if (is_base_case(P)) {
			return base_case_value(P);
	}
		if (memory.find(P) != memory.end()) {
			return memory[P];
	}
		value result = some value;
		for (problem Q in subproblems(P)) {
			result = combine(result, dp(Q));	
		}
		memory[P] = result;
		return result;
}

//f[i][j]表示i个物品，容量j背包的物品最大价值
//若f[i][j] == f[i-1][j],说明不装第i个
//否则装入第i个，同时容量-w,价值+v,w,v分别为第i个物品的重量和价值

f[i][j] = max(f[i-1][j],f[i-1][j-w]+v);

int main(){
    double capa;
    int n;
    while(cin>>capa&&cin>>n){
        int capacity = floor(capa);
        vector<vector<int>>f(n+1,vector<int>(capacity+1,0));
        values.assign(n+1,0);
        weights.assign(n+1,0);
        for(int i=1;i<=n;i++){
            int v,w;
            cin>>v>>w;
            weights[i] = w;
            values[i] = v;
        }

        for(int i=1;i<=n;i++){
            int v = values[i];
            int w = weights[i];
            for(int j=1;j<=capacity;j++){
                if(j<w){
                    f[i][j] = f[i-1][j];
                    continue;
                }
                f[i][j] = max(f[i-1][j],f[i-1][j-w]+v);
            }
        }

        //打印最终装入的物品的index！ 即寻找f[i][j]!=f[i-1][j]
        vector<int>res;
        int j = capacity;
        for(int i=n;i>=1;i--){
            if(f[i][j]!=f[i-1][j]){
                res.push_back(i-1);
                j-=weights[i];
            }
        }
        cout<<res.size()<<endl;
        for(auto i:res)
            cout<<i<<" ";
        cout<<endl;
    }
}

int A[30][30][30];

int w(int a,int b,int c){
    if(a<=0||b<=0||c<=0){
        return 1;
    }
    if(a>20||b>20||c>20){
        return w(20,20,20);
    }
    if(A[a][b][c])  //if already in A no need to do recursion
        return A[a][b][c];
    if(a<b&&b<c){
        A[a][b][c] =w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c); //A[a][b][c-1]+A[a][b-1][c-1]-A[a][b-1][c];
    }
    else
        A[a][b][c] = w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);//A[a-1][b][c]+A[a-1][b-1][c]+A[a-1][b][c-1]-A[a-1][b-1][c-1];
    return A[a][b][c];
}

int main(){

    memset(A,0,sizeof(A));
    while(true){
        int a,b,c;
        cin>>a>>b>>c;
        if(a==-1&&b==-1&&c==-1)
            break;
        cout<<w(a,b,c)<<endl;
    }
    
}

int shortest,num;
int startx,starty;
struct node{
    int x;
    int y;
};
vector<node>vec;
int visited[MAX];

int dis(int x1,int y1,int x2,int y2){
    return abs(x1-x2)+abs(y1-y2);
}

void DFS(int cur,int len,int n){

    if(n==num){
        int t = dis(vec[cur].x,vec[cur].y,startx,starty);
        if(len+t<shortest){
            shortest = len+t;
        }
    }else if(len<shortest){
        int i;
        for(i=0;i<num;i++){
            if(visited[i]==0){
                visited[i] = 1;
                DFS(i,len+dis(vec[cur].x,vec[cur].y,vec[i].x,vec[i].y),n+1);
                visited[i] = 0;
            }
        }
    }


}


int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);


    int sc;
    int row,col;
    cin>>sc;
    while(sc--){
        cin>>row>>col;
        cin>>startx>>starty;
        cin>>num;
        vec.clear();
        for(int i=0;i<num;i++){
            int xx,yy;
            cin>>xx>>yy;
            vec.push_back({xx,yy});
        }
        shortest = INF;
        memset(visited,0,sizeof(visited));

        for(int i=0;i<num;i++){
            int tempL = dis(vec[i].x,vec[i].y,startx,starty);
            visited[i] = 1;
            DFS(i,tempL,1);
            visited[i] = 0;
        }
        cout<<shortest<<endl;
    }
}

int minFallingPathSum(vector<vector<int>>& A) {
    int res = INT_MAX;
    int row = A.size();
    int col = A[0].size();
    int dp[row][col+2];
   
    for(int i=1;i<row;i++){
        for(int j=0;j<col;j++){
            if(j==0){
                A[i][j] = A[i][j]+min(A[i-1][j],A[i-1][j+1]);
            }
            else if(j==col-1){
                A[i][j] = A[i][j]+min(A[i-1][j],A[i-1][j-1]);
            }
            else
               A[i][j] = A[i][j]+min(A[i-1][j],min(A[i-1][j-1],A[i-1][j+1]));
        }
    }
    
    for(int i=0;i<col;i++){
        res = min(res,A[row-1][i]);
    }
    return res;
    
}

void unix_error(char *msg) /* Unix-style error */
{
    fprintf(stderr, "%s: %s\n", msg, strerror(errno));
    exit(0);
}


pid_t Fork(void)
{
    pid_t pid;
    if ((pid = fork()) < 0)
        unix_error("Fork error");
    return pid;
}

void forkandkill()
{
    pid_t pid[N];
    int i;
    int child_status;
    
    for (i = 0; i < N; i++)
        if ((pid[i] = fork()) == 0)
            while(1) ;  // 死循环
    
    for (i = 0; i < N; i++)
    {
        printf("Killing process %d\n", pid[i]);
        kill(pid[i], SIGINT);
    }
    
    for (i = 0; i < N; i++)
    {
        pid_t wpid = wait(&child_status);
        if (WIFEXITED(child_status))
 printf("Child %d terminated with exit status  %d\n",wpid,WEXITSTATUS(child_status));
        else
            printf("Child %d terminated abnormally\n", wpid);
    }
}

void unix_error(char *msg) /* Unix-style error */
{
    fprintf(stderr, "%s: %s\n", msg, strerror(errno));
    exit(0);
}


void sigint_handler(int sig) // SIGINT 处理器
{
    printf("想通过 ctrl+c 来关闭我？\n");
    sleep(2);
    fflush(stdout);
    sleep(1);
    printf("OK. :-)\n");
    exit(0);
}
int main()
{
    // 设定 SIGINT 处理器
    if (signal(SIGINT, sigint_handler) == SIG_ERR)
        unix_error("signal error");
        
    // 等待接收信号
    pause();
    return 0;
}

sigset_t mask, prev_mask;
Sigemptyset(&mask); // 创建空集
Sigaddset(&mask, SIGINT); // 把 SIGINT 信号加入屏蔽列表中
// 阻塞对应信号，并保存之前的集合作为备份
Sigprocmask(SIG_BLOCK, &mask, &prev_mask);
...
... // 这部分代码不会被 SIGINT 中断
...
// 取消阻塞信号，恢复原来的状态
Sigprocmask(SIG_SETMASK, &prev_mask, NULL);

setjmp 保存当前程序的堆栈上下文环境(stack context)，注意，这个保存的堆栈上下文环境仅在调用 setjmp 的函数内有效，如果调用 setjmp 的函数返回了，这个保存的堆栈上下文环境就失效了。调用 setjmp 的直接返回值为 0。


longjmp 将会恢复由 setjmp 保存的程序堆栈上下文，即程序从调用 setjmp 处重新开始执行，不过此时的 setjmp 的返回值将是由 longjmp 指定的值。注意longjmp 不能指定0为返回值，即使指定了 0，longjmp 也会使 setjmp 返回 1。

jmp_buf env;
P1()
{
    if (setjmp(env))
    {
        // 跳转到这里
    } else 
    {
        P2();
    }
    
}
P2()
{
    ...
    P2();
    ...
    P3();
}
P3()
{
    longjmp(env, 1);
}

jmp_buf env;
P1()
{
    P2(); P3();
}
P2()
{
    if (setjmp(env))
    {
        // 跳转到这里
    }
}
P3()
{
    longjmp(env, 1);
}

void end(){
  
      printf("2");fflush(stdout);
  }
  
  int main()
  {
     if(fork()==0)
        atexit(end);
     if(fork()==0){
        printf("0");fflush(stdout);
      }
     else{
        printf("1");fflush(stdout);
     }
      exit(0);
  }

GDT和IDT只有一个，GDTR 和 IDTR指向各自起始的地方，根据TR取GDT中的TSS描述符的时候，GDTR给出首地址

#include <unistd.h>
#include <sys/mman.h>
char *bufp

//fd 为open函数返回的文件描述符
void *mmap(void *start,size_t length,int prot,int flags,int fd,off_t offset)


//创建一个包含size字节的只读，私有，请求二进制0的虚拟内存区域，如果调用成功，bufp则为新区域的地址
bufp = Mmap(NULL,size,PROT_READ,MAP_PRIVATE|MAP_ANON,0,0);

#include <csapp.h>

void mmapcopy(int fd,int size){
    char *bufp;
    bufp = Mmap(NULL,size,PROT_READ,MAP_PRIVATE,fd,0);
    Write(1,bufp,size);
    return;
}


int main(int argc,char **argv){
    if(argc!=2){
        printf("usage: %s <filename>\n",argv[0]);
    }
    
    int fd;
    struct stat stat;
    fd = Open(argv[0],O_RDONLY,0);
    fstat(fd,&stat);
    mmapcopy(fd,stat.st_size);
    exit(0);
}

int mummap（void *start,size_t length）;

0(%esp),%ebp 
%esp +4

1.pushl %ebp #save the caller's ebp

2.movl %esp,%ebp  #set callee's ebp

3.subl $16,%esp   # add 16 bytes, add temporary space

4.movl 8(%ebp),%edx  # set edx = x

5.movl $1,-4(%ebp)

movq $1,%rdi
leaq 16(%rsp),%rsi
movl $2,%rdx
leaq 24(%rsp),%rcx
movl $3,%r8
leaq 28(%rsp),%r9
movl $4,(%rsp)     #Arg 7
leaq 31(%rsp),%rax
movq %rax,8(%rsp)  #Arg 8

movswl 28(%rsp),%eax # %eax = x3

movsbl 31(%rsp),%edx # %edx = x4

s 表示 signextend

		.data  # 数据变量声明
		
        .text  #代码段
        
main:   主函数入口

.data
array: .space 1024
input_msg: .asciiz "Enter the number of integers:\n"
input_int_msg: .asciiz "Enter integers to be sorted\n"
output_msg: .asciiz "the sorted numbers are\n"


.text
.globl main

main:
	la $a0,input_msg
	li $v0,4
	syscall
	 
	li $v0,5  #接受用户输入的数组长度
	syscall
	

	
	la $t6,array #数组首地址
	move $t7,$zero #循环变量i
	move $t8,$zero #循环变量j
	move $t9,$v0  #数组长度

	addi $t3,$zero,1
	beq $v0,$t3,special
			
input:

	la $a0,input_int_msg
	li $v0,4
	syscall
	
	
	li $v0,5  
	syscall
	
	#for(int i=0;i<num;i++)
        #cin>>arr[i];
        
        move $t0,$t7 #$t0 is i
        sll $t0,$t0,2 #i become byte offset
        move $t1,$t6 #$t1 is &array[0]
        add $t1,$t1,$t0 #$t1 is &array[i]
        sw $v0,0($t1) #cin>>array[i]
	
	addi $t7,$t7,1
	blt $t7,$t9,input #if ++i<length
 
	move $t7,$zero
	
loop1:	# 每次外层循环比内层循环的循环变量设为0
	move $t8,$zero
loop2:
	#read arr[j+1] and arr[j]
	
	move $t2,$t8 #t2 is j
	sll $t2,$t2,2 #j=*4;
	addu $t1,$t2,$t6 #&arr[j]
	lw $t4,0($t1)  #arr[j]
	
	
	addi $t2,$t8,1 #j+1
	sll $t2,$t2,2 #(j+1)*4
	addu $t0,$t2,$t6 #&arr[j+1]
	lw   $t5,0($t0) #$t5 = arr[j+1]
	
	
	bge $t5,$t4,skip #if arr[j+1]>arr[j] skip

	sw  $t5,0($t1)
	sw  $t4,0($t0)
	
skip:
	
	
	addi $t8,$t8,1 #j++
	subi $t1,$t9,1 #t1 = num-1
	sub  $t1,$t1,$t7 #t1 = num-1-i
	blt  $t8,$t1,loop2 # if j<num-i-1 t2=1
	addi $t7,$t7,1 #i++
	sub  $t3,$t9,1
	blt  $t7,$t3,loop1  #if i<num-1 then continue loop1
	j output
	
special:
	la $a0,input_int_msg
	li $v0,4
	syscall
	
	
	li $v0,5  
	syscall
	
	#for(int i=0;i<num;i++)
        #cin>>arr[i];
        
        move $t0,$t7 #$t0 is i
        sll $t0,$t0,2 #i become byte offset
        move $t1,$t6 #$t1 is &array[0]
        add $t1,$t1,$t0 #$t1 is &array[i]
        sw $v0,0($t1) #cin>>array[i]
	
output:
	
	la $a0,output_msg
	li $v0,4
	syscall
	
	move $t7,$zero
print:
	
	move $t0,$t7
	
	sll $t0,$t0,2
	
	add $t1,$t6,$t0
	
	lw $a0,0($t1) #argument a0
	
	li $v0,1
	syscall
	
	addi $t7,$t7,1
	blt $t7,$t9,print

method 1: time complexity O(Nlog(k))

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        
        multiset<int>st;
        vector<int>vec;
        list<int> lst;
        for(int i=0;i<nums.size();i++){
            if(i-k>=0){
                int top = lst.front();
                lst.pop_front();
                st.erase(st.find(top));
            }
         
            lst.push_back(nums[i]);
            st.insert(nums[i]);
              if(i-k>=-1){
                vec.push_back(*st.rbegin());
            }
            
        }
        
        return vec;
        
    }
};


method 2

1. use a deque to store the index in the window , each window must fall in the range(i-k+1,i). so whenever an index smaller than i-k+1,pop_front() to discard the element; 

2. when insert a new element nums[i], compare it with the top of the queue , until q[front]>nums[i] ,that is to say, q[front] is always the max element in the window

  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
       
         deque<int>dq;
         vector<int>res;
         if(nums.empty())
             return res;
         for(int i=0;i<nums.size();i++){
            while(!dq.empty()&&dq.front()<i-k+1){
                dq.pop_front();
            }
            //remove smaller elements in window
            while(!dq.empty()&&nums[dq.back()]<=nums[i]){
                dq.pop_back();
            }
             dq.push_back(i);
             if(i-k+1>=0){
                 res.push_back(nums[dq.front()]);
             }
         }
         return res;
        
    }

int main(){

    int P,T;
    cin>>P>>T;
    vector<vector<ip>> adj(P);
    vector<vector<ip>> parent(P);
    vector<int>distStart(P,INF);
    vector<int>distEnd(P,INF);
    vector<tuple<int,int,int>>edgeVec;

    for(int i=0;i<T;i++){
        int from,to,w;
        cin>>from>>to>>w;
        edgeVec.push_back(make_tuple(from,to,w));
        adj[from].push_back(make_pair(to,w));
        adj[to].push_back(make_pair(from,w));
    }

    dijkstra(adj,distStart,0);
    dijkstra(adj,distEnd,P-1);

    int shortestPath = distStart[P-1];
    int ans=0;
    for(int i=0;i<T;i++){
        int from = get<0>(edgeVec[i]);
        int to = get<1>(edgeVec[i]);
        int weight = get<2>(edgeVec[i]);

        if(distStart[to]+distEnd[from]+weight==shortestPath||
        distStart[from]+distEnd[to]+weight==shortestPath){
            ans+=weight;
        }

    }

    cout<<ans*2;

    return 0;
}