Understanding the nature of high-redshift dusty galaxies requires a comprehensive view of their interstellar medium (ISM) and molecular complexity. However, the molecular ISM at high redshifts is commonly studied using only a few species beyond (CO)-C-12-O-16, limiting our understanding. In this paper, we present the results of deep 3 mm spectral line surveys using the NOrthern Extended Millimeter Array (NOEMA) targeting two strongly lensed dusty galaxies observed when the Universe was less than 1.8 Gyr old: APM 08279+5255, a quasar at redshift z = 3.911, and NCv1.143 (H-ATLAS J125632.7+233625), a z = 3.565 starburst galaxy. The spectral line surveys cover rest-frame frequencies from about 330 to 550 GHz for both galaxies. We report the detection of 38 and 25 emission lines in APM 08279+5255 and NCv1.143, respectively. These lines originate from 17 species, namely CO, (CO)-C-13, (CO)-O-18, CN, CCH, HCN, HCO+, HNC, CS, (CS)-S-34, H2O, H3O+, NO, N2H+, CH, c-C3H2, and the vibrationally excited HCN and neutral carbon. The spectra reveal the chemical richness and the complexity of the physical properties of the ISM. By comparing the spectra of the two sources and combining the analysis of the molecular gas excitation, we find that the physical properties and the chemical imprints of the ISM are different: the molecular gas is more excited in APM 08279+5255, which exhibits higher molecular gas temperatures and densities compared to NCv1.143; the molecular abundances in APM 08279+5255 are akin to the values of local active galactic nuclei (AGN), showing boosted relative abundances of the dense gas tracers that might be related to high-temperature chemistry and/or the X-ray-dominated regions, while NCv1.143 more closely resembles local starburst galaxies. The most significant differences between the two sources are found in H2O: the 448 GHz ortho-H2O(4(23) - 3(30)) line is significantly brighter in APM 08279+5255, which is likely linked to the intense far-infrared radiation from the dust powered by AGN. Our astrochemical model suggests that, at such high column densities, far-ultraviolet radiation is less important in regulating the ISM, while cosmic rays (and/or X-rays and shocks) are the key players in shaping the molecular abundances and the initial conditions of star formation. Both our observed CO isotopologs line ratios and the derived extreme ISM conditions (high gas temperatures, densities, and cosmic-ray ionization rates) suggest the presence of a top-heavy stellar initial mass function. From the similar to 330-550 GHz continuum, we also find evidence of nonthermal millimeter flux excess in APM 08279+5255 that might be related to the central supermassive black hole. Such deep spectral line surveys open a new window into the physics and chemistry of the ISM and the radiation field of galaxies in the early Universe.